Longest Palindromic Substring - Amazon Top Interview Questions

                        Solution in C++ :

class Solution {
    vector<vector<int>> memo;
    int dp(string &s, int i, int j) {
        if (i > j) return 0;
        if (i == j) return 1;
        if (memo[i][j] != -1)  // Return precaluclated value.
            return memo[i][j];
        // When s[i]==s[j] and the maximum palindrome in between is of length j-i-1 (This means
        // string i+1,j-1 is a palindrome) return current length.
        if (s[i] == s[j] && dp(s, i + 1, j - 1) == j - 1 - i) return memo[i][j] = j - i + 1;
        // When current substring is not a pallindrome return max palindrome between (i,j-1) and
        // (i+1,j)
        return memo[i][j] = max(dp(s, i, j - 1), dp(s, i + 1, j));
    }

    public:
    int solve(string &s) {
        memo.resize(s.length(), vector<int>(s.length(), -1));
        return dp(s, 0, s.length() - 1);
    }
};
int solve(string s) {
    return Solution().solve(s);
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public int solve(String s) {
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = helper(s, i, i);
            int len2 = helper(s, i, i + 1);
            res = Math.max(len1, Math.max(len2, res));
        }
        return res;
    }

    public int helper(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        return r - l - 1;
    }
}
                    

                        Solution in Python : 
                            
def manacher(s):
    t = "#".join([""] + list(s) + [""])
    m = len(t)
    a = [0] * m
    l = 0
    r = -1
    for i in range(m):
        j = 1 if i > r else min(r - i + 1, a[l + r - i])
        while i >= j and i + j < m and t[i - j] == t[i + j]:
            j += 1
        a[i] = j
        j -= 1
        if i + j > r:
            l = i - j
            r = i + j
    return a


class Solution:
    def solve(self, s):
        return max(manacher(s)) - 1