214. Shortest Palindrome

Problem Statement

You are given a string s. You can convert s to a

palindrome by adding characters in front of it.

Return the shortest palindrome you can find by performing this transformation.

Example 1:

Input: s = "aacecaaa"
Output: "aaacecaaa"

Example 2:

Input: s = "abcd"
Output: "dcbabcd"

Constraints:

0 <= s.length <= 5 * 104
s consists of lowercase English letters only.

Intuition

Approach : KMP Prefix suffix

s = anab
Output = b)anab

reverse String  = bana
Attach at end

anab#bana
Run longest Prefix Suffix, by that we can come to know about longest match aba
and we can eliminate that
and just put that extra b at start again to get

banab

Video Links

Approach 1:

KMP

C++

class Solution {
public:
    string shortestPalindrome(string s) {
        if(s.size() == 0)   return "";
        string rev = s;
        reverse(rev.begin(), rev.end());
        // Make a distinction, otherwise it'll match entire
        string temp = s + "#" + rev;

        // Apply LPS KMP
        vector<int> lps(temp.size(), 0);
        int prev=0, i=1;

        while(i<temp.size()){
            if(temp[i] == temp[prev]){
                lps[i] = prev + 1;
                prev++; i++;
            }
            else if(prev == 0){
                lps[i] = 0;
                i++;
            }
            else
                prev = lps[prev-1];
        }

        int last_val = lps.back();

        return rev.substr(0, rev.size() - last_val) + s;
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++