Palindrome Problems — Expand Around Centre, DP, and Manacher

Palindrome Problem Hierarchy

Problem	Approach	Complexity
Valid palindrome	Two pointers	O(n)
Longest palindromic substring	Expand / Manacher	O(n)
Count palindromic substrings	Expand around centres	O(n²)
Palindrome partitioning	Backtrack + DP	O(n·2^n)
Min cuts palindrome partition	DP + Manacher	O(n²)

Count Palindromic Substrings — Expand Around Centres

def countSubstrings(s):
    count = 0
    def expand(l, r):
        nonlocal count
        while l >= 0 and r < len(s) and s[l] == s[r]:
            count += 1
            l -= 1; r += 1
    for i in range(len(s)):
        expand(i, i)
        expand(i, i+1)
    return count

Palindrome Partitioning — Backtracking

def partition(s):
    res = []
    def backtrack(start, path):
        if start == len(s): res.append(path[:])
        for end in range(start+1, len(s)+1):
            sub = s[start:end]
            if sub == sub[::-1]:
                path.append(sub)
                backtrack(end, path)
                path.pop()
    backtrack(0, [])
    return res

Minimum Cuts — DP O(n²)

def minCut(s):
    n = len(s)
    is_pal = [[False]*n for _ in range(n)]
    for i in range(n-1, -1, -1):
        for j in range(i, n):
            if s[i]==s[j] and (j-i<=2 or is_pal[i+1][j-1]):
                is_pal[i][j] = True

    cuts = list(range(-1, n))
    for i in range(1, n):
        for j in range(i+1):
            if is_pal[j][i]:
                cuts[i+1] = min(cuts[i+1], cuts[j]+1)
    return cuts[n]

JavaScript

function countSubstrings(s){
    let count=0;
    const exp=(l,r)=>{while(l>=0&&r<s.length&&s[l]===s[r]){count++;l--;r++;}};
    for(let i=0;i<s.length;i++){exp(i,i);exp(i,i+1);}
    return count;
}

Java

public int countSubstrings(String s){
    int[]count={0};
    java.util.function.BiConsumer<Integer,Integer>exp=(l,r)->{int L=l,R=r;while(L>=0&&R<s.length()&&s.charAt(L)==s.charAt(R)){count[0]++;L--;R++;}};
    for(int i=0;i<s.length();i++){exp.accept(i,i);exp.accept(i,i+1);}
    return count[0];
}

C++

int countSubstrings(string s){
    int n=s.size(),count=0;
    auto expand=[&](int l,int r){while(l>=0&&r<n&&s[l]==s[r]){count++;l--;r++;}};
    for(int i=0;i<n;i++){expand(i,i);expand(i,i+1);}
    return count;
}

C

int countSubstrings(char*s){int n=strlen(s),count=0;for(int i=0;i<n;i++){for(int d=0;i-d>=0&&i+d<n&&s[i-d]==s[i+d];d++)count++;for(int d=0;i-d>=0&&i+d+1<n&&s[i-d]==s[i+d+1];d++)count++;}return count;}