31. Shortest Palindrome(Imp)

Minimum addition to make string palindrome

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"

Approach:

If we find the maximum length palindromic substring from front. We can add reverse of the right part to make it palindrome. To find maximum length palindrome in O(n +m) time

Solution: (Comparing every possible length)

class Solution
{
public:
    bool isPalin(string s)
    {
        int i = 0;
        int j = s.length() - 1;

        while (i <= j)
        {
            if (s[i] != s[j])
            {
                return false;
                
            }
            i++;
            j--;
        }

        return true;
    }

    string shortestPalindrome(string s)
    {

        int n = s.length();
        if(n == 0){
            return "";
        }
        string res = "";
        int minLen = INT_MAX;

        for (int i = 1; i <= n; i++)
        {

            string ls = s.substr(0, i);
            string rs = s.substr(i, n - i);

            if (isPalin(ls))
            {
                string temp = rs;
                reverse(rs.begin(), rs.end());
                string str = rs + ls + temp;

                if (str.length() < minLen)
                {
                    res = str;
                    minLen = str.length();
                }
            }
        }

        return res;
    }
};

Time Complexity: O(n * n)

Solution: ()