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.

&nbsp;
Example 1:
Input: s = "aacecaaa"
Output: "aaacecaaa"
Example 2:
Input: s = "abcd"
Output: "dcbabcd"

&nbsp;
Constraints:


	0 &lt;= s.length &lt;= 5 * 104
	s consists of lowercase English letters only.


class Solution:
    def shortestPalindrome(self, s: str) -> str:
        
        end = 0
        
        # if the string itself is a palindrome return it
        if(s == s[::-1]):
            return s
        
        # Otherwise find the end index of the longest palindrome that starts
        # from the first character of the string
        
        for i in range(len(s)+1):
            if(s[:i]==s[:i][::-1]):
                end=i-1
        
        # return the string with the remaining characters other than
        # the palindrome reversed and added at the beginning
        
        return (s[end+1:][::-1])+s
class Solution {
    public String shortestPalindrome(String s) {
        for(int i=s.length()-1; i >= 0; i--){
            if(isPalindrome(s, 0, i)){
                String toAppend = s.substring(i+1);
                String result = new StringBuilder(toAppend).reverse().append(s).toString();
                return result;
            }
        }
        String result = new StringBuilder(s).reverse().append(s).toString();
        return result;        
    }
    
    boolean isPalindrome(String s, int left, int right){
        while(left < right){
            if(s.charAt(left) != s.charAt(right))
                return false;
            left++;
            right--;
        }
        return true;
    }
}
class Solution {
public:
    string shortestPalindrome(string s) {
        
        int BASE = 26, MOD = 1e9+7;
        int start = s.size()-1;
        
        // Calculate hash values from front and back
        long front = 0, back = 0;
        long power = 1;
        
        for(int i=0; i<s.size(); i++){
            front = (front*BASE + (s[i]-'a'+1))%MOD;
            back = (back*BASE + (s[start--]-'a'+1))%MOD;
            power = (power*BASE)%MOD;
        }
        
        // If hash values of both front and back are same, then it is a palindrome
        if(front == back){
            return s;
        }
        
        // As it is not palindrome, add last characters in the beginning, and then check.
        // Store the hash value of the newly added characters from front and back
        
		// new_front will be added to front to get new hash value
        // new_back will be added to back to get new hash value 
        long new_front = 0, new_back = 0;
        long new_power = 1;
		
		int end=s.size()-1;
        string ans = "";
        
        while(end >= 0){
			// Taking character from ending 
            int ch = (s[end]-'a'+1);
            
            new_front = (new_front*BASE + ch*power) % MOD;
            new_back = (ch*new_power + new_back) % MOD;
            new_power = (new_power*BASE) % MOD;
            
            int final_front = (new_front + front) % MOD;
			back = (back*BASE) % MOD;
            int final_back = (new_back + back) % MOD;
                
			// Storing it in separate string
            ans += s[end];
            end--;
            
			// Both hashes are same
            if(final_front == final_back){
                break;
            }
        }
        return ans+s;
    }
};
var shortestPalindrome = function(s) {
    const rev = s.split('').reverse().join('');
    const slen = s.length;

    const z = s + '$' + rev;
    const zlen = z.length;

    const lpt = new Array(zlen).fill(0);

    for(let i = 1; i < zlen; i++) {
        let j = lpt[i-1];

        while(j > 0 && z.charAt(i) != z.charAt(j))
            j = lpt[j-1];

        if(z.charAt(i) == z.charAt(j))
            j++;

        lpt[i] = j;
    }

    return rev.slice(0, slen - lpt.at(-1)) + s;
};
Shortest Palindrome