214 - Shortest 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"

Constraints:

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

Algorithm

• In the worst-case scenario, where there are no identical characters in the string s, the minimum number of characters required to be added is s.size() - 1.
• In the first example, the string contains a palindrome. To form a complete palindrome, only one character needs to be added to the front.

To solve this, first reverse the string s to obtain t. Then, compare the original string s with the reversed string t, starting from the first character and proceeding one character at a time:

• If they are equal, it indicates that s is already a palindrome. No additional characters need to be added, and the function can return immediately.
• If they are not equal, remove the last character from s, remove the first character from t, and continue comparing. This process repeats until the strings are equal or the loop concludes.

This method ensures that the two strings are concatenated in the correct manner to form a palindrome.

Examples:

Worst Case: “abcda”+”adcba”

Reversed:  a b c d a
s:                   a d c b a

Try to move both towards the center to find a possible overlap. By removing one character, we save an “a”.

Reversed:  a b c d a
s:                 a d c b a

Move further, “da” and “ad” overlap, and the remaining part, “abc” vs “cba”, forms a palindrome.

Reversed:  a b c d a
s:               a d c b a

Therefore, “da” and “ad” go to the next recursion.

Reversed:  d a
s:             a d

Moving one more character aligns the strings perfectly, yielding the final result.

• “abc”+dfs()+”cba” => “abc”+”dad”+”cba”

  Reversed:  d a
  s:           a d
  

Another Example: “aacecaaa”

• The iteration stops at the last ‘a’, i=7.
• "a"+dfs("aacecaa")+"a"

This approach strategically reduces the problem size by identifying overlapping parts between the original and reversed strings, effectively minimizing the number of characters needed to transform the input into a palindrome. 

Code:-

C++

class Solution {
public:
    string shortestPalindrome(string s) {
        unsigned d = 16777619, h = 0, rh = 0, p = 1, maxLen = 0;
        for (int i = 0; i < s.size(); ++i) {
            h = h * d + s[i] - 'a';
            rh += (s[i] - 'a') * p;
            p *= d;
            if (h == rh) maxLen = i + 1;
        }
        return string(rbegin(s), rbegin(s) + s.size() - maxLen) + s;
    }
};

JAVA

public class Shortest_Palindrome {


    public class Solution {
        public String shortestPalindrome(String s) {

            if (s == null || s.length() == 0) {
                return "";
            }

            int i = 0, n = s.length();
            for (int j = n - 1; j >= 0; --j) { // @note: j will cross i, eg. making i=2 for "adcba"
                if (s.charAt(i) == s.charAt(j)) {
                    ++i;
                }
            }
            // now [0, i) is a possible palindrome, but need extra check
            if (i == n) {
                return s;
            }

            String remaining = s.substring(i); // need to add reverse part of it
            String rem_rev = new StringBuilder(remaining).reverse().toString();
            return rem_rev + shortestPalindrome(s.substring(0, i)) + remaining;

        }
    }
}

############

class Solution {
    public String shortestPalindrome(String s) {
        int base = 131;
        int mul = 1;
        int mod = (int) 1e9 + 7;
        int prefix = 0, suffix = 0;
        int idx = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            int t = s.charAt(i) - 'a' + 1;
            prefix = (int) (((long) prefix * base + t) % mod);
            suffix = (int) ((suffix + (long) t * mul) % mod);
            mul = (int) (((long) mul * base) % mod);
            if (prefix == suffix) {
                idx = i + 1;
            }
        }
        if (idx == n) {
            return s;
        }
        return new StringBuilder(s.substring(idx)).reverse().toString() + s;
    }
}