Number of Palindromic Substrings - Amazon Top Interview Questions

                        Solution in C++ :

int solve(string s) {
    int count = 0;
    for (int i = 0; i < s.size(); i++) {
        int j = i - 1, k = i;
        while (j >= 0 && k < s.size() && s[j] == s[k]) {
            count++;
            j--;
            k++;
        }
        j = i, k = i;
        while (j >= 0 && k < s.size() && s[j] == s[k]) {
            count++;
            j--;
            k++;
        }
    }
    return count;
}
                    

                        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 u = expand(s, i, i + 1); // even
            int v = expand(s, i, i); // odd
            res += u / 2;
            res += v / 2;
        }
        res += s.length();
        return res;
    }

    public int expand(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 : 
                            
class Solution:
    def solve(self, s):
        def isP(s):
            return s == s[::-1]

        @lru_cache(None)
        def dp(s):
            count = 0

            if len(s) == 1:
                return 1

            for j in range(1, len(s) + 1):
                if isP(s[:j]):
                    count += 1

            return count + dp(s[1:])

        return dp(s)