 # Minimum Characters required to make a String Palindromic

Aug 5th, 2022
1,149
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. '''
2. We can solve this problem efficiently in O(n) time and O(1) space.
3. Approach : Take left pointer as 0 and right and n-1 and compare both characters
4. If both are same left++ and right–;
5. else
6. we can think that we have to add N-right elements at front to make last (N-right) characters palindrome so added = (n-right)
7. Now left again point to 0 as we have to check the string from 0th index .
8. but while the character at right position is same as 0th index char then we can add one less character at front  and left will increase by 1.
9. '''
10.
11. class Solution:
12.     # @param A : string
13.     # @return an integer
14.     def solve(self, a):
15.         n=len(a)
16.         l,r=0,n-1
18.         while l<r:
19.             if a[l]==a[r]:
20.                 l,r=l+1,r-1
21.             else:
22.                 l=0
24.                 while a[l]==a[r]:#this while loop decreases the redundant characters that we added which already useful in making palindrome
25.                     l=l+1
27.                 r-=1#Finally we should reduce the actual r because we have added sufficent chracters from back
28.
30.  '''
31. e.g. a c a a
32.       |     |
33.       a c a a
34.         | |
35.      a a =a c a a  #Before equal we added required chraracters to make it palindrome
36.           |   |
37.
38.      a a =a   c   a a
39.        x     | |
40.      final a a c a a
41.