Advertisement
Iam_Sandeep

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!
Python 1.47 KB | None
  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
  17.         added =0
  18.         while l<r:
  19.             if a[l]==a[r]:
  20.                 l,r=l+1,r-1
  21.             else:
  22.                 l=0
  23.                 added=n-r #we will add a[r:][::-1] to start
  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
  26.                     added-=1
  27.                 r-=1#Finally we should reduce the actual r because we have added sufficent chracters from back
  28.                
  29.         return added
  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.      
  42.      added =1    
  43. '''
  44.  
Advertisement
RAW Paste Data Copied
Advertisement