Problem Statement

Given an string A. The only operation allowed is to insert characters in the beginning of the string.

Find how many minimum characters are needed to be inserted to make the string a palindrome string.

Input Format

The only argument given is string A.

Output Format

Return the minimum characters that are needed to be inserted to make the string a palindrome string.

For Example

`Input 1: A = "ABC" Output 1: 2 Explanation 1: Insert 'B' at beginning, string becomes: "BABC". Insert 'C' at beginning, string becomes: "CBABC".

Input 2: A = "AACECAAAA" Output 2: 2 Explanation 2: Insert 'A' at beginning, string becomes: "AAACECAAAA". Insert 'A' at beginning, string becomes: "AAAACECAAAA".`

Problem Link

Minimum Characters required to make a String Palindromic - InterviewBit

Code

// Time Complexity : O(n^2)
// Space Complexity : O(n^2)

typedef long long int ll;
int Solution::solve(string s) {
 
    ll n = s.size();
    reverse(s.begin(),s.end());
 
    vector<vector<bool>> isP(n,vector<bool>(n,false));
 
    for(ll gap=0;gap<n;gap++)
        {
            for(ll i=0,j=gap;j<n;i++,j++)
            {
                if(!gap)
                    isP[i][j] = true;
                
                else if(gap==1)
                {
                    if(s[i]==s[j])
                        isP[i][j] = true;
                    else
                        isP[i][j] = false;
                }
                
                else
                {
                    if(s[i]==s[j])
                        isP[i][j] = isP[i+1][j-1];
                    else
                        isP[i][j] = false;
                }
            }
        }
 
       long long  int res = 0;
 
        for(ll i=0;i<n;i++)
        {
            if(isP[i][n-1])
            break;
 
            res++;
        }
 
        return res;
}

Optimized Version

// Time Complexity : O(n)
// Space Complexity : O(1)

typedef long long int ll;
int Solution::solve(string A) {

int l=0, r=A.length()-1;
int count = 0;
while(l < r){
    if(A[l] == A[r]){
        l++;
        r--;
    }else{
        if(l == 0) {
            count++;
            r--;
        }
        else {
            count += l;
            l = 0;
        }
        
    }
}
 
return count;
}