Shortest Palindrome

In the shortest palindrome problem, we have given a string s of length l. Add characters in front of it to make it palindrome if it’s not. Print the smallest count of characters used to make the given string a palindrome.

Example

Input : s = abc

Output: 2  (by adding c and b in front will result in palindrome cbabc)

Input : s = abbaa

Output: 1  (by adding a front will result in palindrome aabbaa)

Simple Method

Algorithm

1. Initialize a string s of length L.
2. Create an integer variable to store the count and a flag variable. Initialize both the variables as 0.
3. Traverse through the string while it’s length is greater than 0. Traverse through the string and start comparing the starting character to the ending character until you reach the middle of the string. If the current string is a palindrome i.e. the starting characters are same as the ending characters, update the flag variable as 1 and break the loop.
4. Else increment the count variable by 1 and remove the last character of the string.
5. If the flag variable is equal to 1, print count.

C++ Program to find the shortest palindrome

#include<bits/stdc++.h> 
using namespace std; 
  
bool isPalindrome(string s){ 
    int l = s.length(); 
    int j; 
      
    for(int i=0, j=l-1; i<=j; i++, j--){ 
        if(s[i] != s[j]) 
            return false; 
    } 
    return true; 
} 
  
int main(){ 
    string s = "abc"; 
    int count = 0, f = 0; 
      
    while(s.length()>0){ 
        if(isPalindrome(s)){ 
            f = 1; 
             break; 
        } 
        else{ 
            count++; 
            s.erase(s.begin() + s.length() - 1); 
        } 
    } 
      
    if(f) 
        cout<<count; 
}

2

Java Program to find the shortest palindrome

class Palindrome{ 
  
    static boolean isPalindrome(String s){ 
        int l = s.length(); 
  
        for(int i=0, j=l-1; i<=j; i++, j--){ 
            if(s.charAt(i) != s.charAt(j)){ 
                return false; 
            } 
        } 
        return true; 
    } 
  
    public static void main(String[] args){ 
        String s = "abc"; 
        int count = 0, f = 0; 
  
        while(s.length() > 0){ 
            if(isPalindrome(s)){ 
                f = 1; 
                break; 
            } 
            else{ 
                count++; 
  
                s = s.substring(0, s.length() - 1); 
            } 
        } 
  
        if(f == 1){ 
            System.out.println(count); 
        } 
    } 
}

2

Complexity Analysis

Time Complexity: O(L*L)   (L is the length of the string)

Auxiliary Space: O(1) because we used constant extra space

Efficient Method

Algorithm

1. Initialize a string s of length L.
2. Create a string variable and store the reverse of the original string in it.
3. Create another string to store the concatenation of the strings and store the concatenation of the original string and the reversed string with a special character in between in it.
4. Initialize an lps array.
5. Traverse through the string and update the values of the lps array.
6. Return the lps array.

C++ Program to find the shortest palindrome

#include <bits/stdc++.h> 
using namespace std; 
  
vector<int> computeLPSArray(string s){ 
    int l = s.length(); 
    vector<int> lps(l); 
  
    int len = 0; 
    lps[0] = 0; 
  
    int i = 1; 
    while(i<l){ 
        if(s[i] == s[len]){ 
            len++; 
            lps[i] = len; 
            i++; 
        } 
        else{ 
            if(len != 0){ 
                len = lps[len-1]; 
            } 
            else{ 
                lps[i] = 0; 
                i++; 
            } 
        } 
    } 
    return lps; 
} 
  
int minChar(string s){ 
    string rev = s; 
    reverse(rev.begin(), rev.end()); 
  
    string concat = s + "$" + rev; 
  
    vector<int> lps = computeLPSArray(concat); 
  
    return(s.length() - lps.back()); 
} 
  
int main(){ 
    string s = "abc"; 
    cout<<minChar(s); 
    return 0; 
}

2

Java Program to find the shortest palindrome

class Palindrome{ 
  
    public static int[] computeLPSArray(String s){ 
        int l = s.length(); 
        int lps[] = new int[l]; 
        int i = 1, len = 0; 
        lps[0] = 0;
          
        while(i < l){ 
            if(s.charAt(i) == s.charAt(len)){ 
                len++; 
                lps[i] = len; 
                i++; 
            } 
            else{ 
                if(len != 0){ 
                    len = lps[len - 1]; 
                } 
                else{ 
                    lps[i] = 0; 
                    i++; 
                } 
            } 
        } 
        return lps; 
    } 
      
    static int minChar(String s){  
        StringBuilder S = new StringBuilder(); 
        S.append(s); 
          
        String rev = S.reverse().toString(); 
        S.reverse().append("$").append(rev); 
          
        int lps[] = computeLPSArray(S.toString()); 
        return s.length() - lps[S.length() - 1]; 
    } 

    public static void main(String[] args){ 
        String s = "abc"; 
        System.out.println(minChar(s)); 
    } 
}

2

Complexity Analysis

Time Complexity: O(L)    (L is the length of the string)

Auxiliary Space: O(L) because we used extra space for L characters.

References