214. Shortest Palindrome

Intuition

This problem accepts a O(n²) solution in leetcode but it would be more fun to look into the O(n) solution. The main observation to make is that the shortest palindrome can be formed finding the longest palindromic prefix. Once you get that info, then you have to append the remaining characters to the beginning of this string in reverse order. A backwards and forward rolling hash can help us find that palindromic prefix in O(n) time.

class Solution {
public:
    const long long base = 26;
    const long long mod = 1e9 + 7;
    string shortestPalindrome(string s) {
        function<long long(long long)> customMod = [&](long long num){
            long long modulo = num;
            modulo %= mod;
            return modulo;
        };
        function<int(char)> getIdx = [&](char c){
            return c-'a';
        };
        string ans = "";
        const long long n = s.size();
        long long left = 0, right = 0, power = 1;
        int palindromicPrefix = -1;
        for(int i = 0; i < n ; i++){
            left = customMod(left * base + getIdx(s[i])); 
            right = customMod(right + power * getIdx(s[i])); 
            power = customMod(power * base);
            if(left == right){
                palindromicPrefix = i;
            }
        }
        string rem = s.substr(palindromicPrefix+1);
        reverse(rem.begin(), rem.end());
        return rem + s;
    }
};