String Palindrome Patterns: Complete Guide

Palindromes are one of the most frequently tested string topics in coding interviews. A palindrome reads the same forwards and backwards — “racecar”, “madam”, “level”. What makes palindrome problems interesting is that they span the entire difficulty spectrum: from a simple two-pointer check to Manacher’s linear-time algorithm that intimidates even experienced engineers.

In this guide we’ll build up from the basics to the advanced, giving you a toolkit that covers every palindrome variant you’re likely to encounter.

1. Checking if a string is a palindrome

The simplest palindrome problem: given a string, determine whether it reads the same forwards and backwards.

The two-pointer approach

Place one pointer at the start and one at the end. Move them inward, comparing characters. If every pair matches, the string is a palindrome.

def is_palindrome(s: str) -> bool:
    """Check if string is a palindrome. O(n) time, O(1) space."""
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

Time complexity: O(n) — we scan at most n/2 pairs. Space complexity: O(1) — just two pointers.

Handling real-world input

Interview problems often ask you to ignore non-alphanumeric characters and treat uppercase and lowercase as the same. LeetCode 125 (“Valid Palindrome”) is exactly this:

def is_palindrome_clean(s: str) -> bool:
    """Valid palindrome ignoring non-alphanumeric and case. O(n) time, O(1) space."""
    left, right = 0, len(s) - 1
    while left < right:
        # Skip non-alphanumeric from left
        while left < right and not s[left].isalnum():
            left += 1
        # Skip non-alphanumeric from right
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True

This still runs in O(n) time because each pointer moves at most n steps total.

Almost palindrome (Valid Palindrome II)

A popular follow-up: given a string, can you make it a palindrome by removing at most one character?

def valid_palindrome_ii(s: str) -> bool:
    """Can we make s a palindrome by removing at most one character? O(n) time."""
    def check(lo, hi):
        while lo < hi:
            if s[lo] != s[hi]:
                return False
            lo += 1
            hi -= 1
        return True

    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            # Try removing either the left or right character
            return check(left + 1, right) or check(left, right - 1)
        left += 1
        right -= 1
    return True

Time complexity: O(n) — the inner check runs at most once and scans the remaining string.

2. Longest palindromic substring

This is one of the most classic interview problems (LeetCode 5). Given a string, find the longest substring that is a palindrome.

Brute force: O(n³)

Check every possible substring and verify if it’s a palindrome. There are O(n²) substrings, and checking each takes O(n). This is too slow for interviews but establishes the baseline.

Expand around center: O(n²)

The key insight: every palindrome has a center. For odd-length palindromes the center is a single character; for even-length palindromes the center is between two characters. There are 2n - 1 possible centers.

For each center, expand outward as long as the characters match:

def longest_palindrome_substring(s: str) -> str:
    """Find longest palindromic substring. O(n²) time, O(1) space."""
    if not s:
        return ""

    start, max_len = 0, 1

    def expand(left: int, right: int):
        """Expand around center and return length of palindrome."""
        nonlocal start, max_len
        while left >= 0 and right < len(s) and s[left] == s[right]:
            current_len = right - left + 1
            if current_len > max_len:
                start = left
                max_len = current_len
            left -= 1
            right += 1

    for i in range(len(s)):
        expand(i, i)       # Odd-length palindromes
        expand(i, i + 1)   # Even-length palindromes

    return s[start:start + max_len]

Time complexity: O(n²) — each expansion takes O(n) in the worst case, and we do 2n expansions. Space complexity: O(1) — no extra data structures.

Manacher’s algorithm: O(n)

Manacher’s algorithm finds the longest palindromic substring in linear time. It’s rarely expected in interviews, but knowing it sets you apart.

The algorithm works on a transformed string with separators inserted between characters (to handle even-length palindromes uniformly), and uses previously computed palindrome information to skip redundant comparisons.

def manachers(s: str) -> str:
    """Longest palindromic substring in O(n) time using Manacher's algorithm."""
    if not s:
        return ""

    # Transform: "abc" -> "^#a#b#c#$"
    # ^ and $ are sentinels that don't match anything
    t = "^#" + "#".join(s) + "#$"
    n = len(t)

    # p[i] = radius of the palindrome centered at t[i]
    p = [0] * n
    center = right = 0  # Center and right boundary of the rightmost palindrome

    for i in range(1, n - 1):
        mirror = 2 * center - i  # Mirror of i around center

        if i < right:
            p[i] = min(right - i, p[mirror])

        # Try to expand
        while t[i + p[i] + 1] == t[i - p[i] - 1]:
            p[i] += 1

        # Update center and right boundary
        if i + p[i] > right:
            center, right = i, i + p[i]

    # Find the maximum element in p
    max_len = max(p)
    center_idx = p.index(max_len)

    # Extract the original substring
    start = (center_idx - max_len) // 2
    return s[start:start + max_len]

Time complexity: O(n) — each character is visited a constant number of times amortized. Space complexity: O(n) — for the transformed string and the p array.

Why does this work? The key insight is the mirror property. If position i falls within a known palindrome centered at center, then the palindrome radius at i is at least as large as at its mirror position — unless it would extend beyond the right boundary. This lets us skip many comparisons.

3. Count palindromic substrings

LeetCode 647 asks: given a string, count how many palindromic substrings it contains. “abc” has 3 (each single character), while “aaa” has 6.

The expand-around-center technique works beautifully here:

def count_palindromic_substrings(s: str) -> int:
    """Count all palindromic substrings. O(n²) time, O(1) space."""
    count = 0

    def expand(left: int, right: int):
        nonlocal count
        while left >= 0 and right < len(s) and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1

    for i in range(len(s)):
        expand(i, i)       # Odd-length
        expand(i, i + 1)   # Even-length

    return count

Each expansion finds all palindromes with a given center, and we sum them up.

DP approach

We can also use a 2D DP table where dp[i][j] is True if s[i:j+1] is a palindrome:

def count_palindromes_dp(s: str) -> int:
    """Count palindromic substrings using DP. O(n²) time and space."""
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    count = 0

    # Every single character is a palindrome
    for i in range(n):
        dp[i][i] = True
        count += 1

    # Check substrings of length 2
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            count += 1

    # Check substrings of length 3 and above
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
                count += 1

    return count

The DP approach uses O(n²) space but gives you the dp table which can be reused for follow-up problems like palindrome partitioning.

4. Palindrome partitioning

Palindrome Partitioning I (LeetCode 131)

Given a string, partition it so that every substring is a palindrome. Return all such partitions.

This is a classic backtracking problem. At each position, we try every possible palindromic prefix and recurse on the remainder:

def partition(s: str) -> list:
    """Return all palindrome partitions. Backtracking approach."""
    result = []

    def is_palindrome(sub: str) -> bool:
        return sub == sub[::-1]

    def backtrack(start: int, path: list):
        if start == len(s):
            result.append(path[:])  # Found a valid partition
            return

        for end in range(start + 1, len(s) + 1):
            substring = s[start:end]
            if is_palindrome(substring):
                path.append(substring)
                backtrack(end, path)
                path.pop()

    backtrack(0, [])
    return result

Time complexity: O(n * 2^n) in the worst case — there are 2^(n-1) ways to partition, and checking palindromes takes O(n).

Optimized with DP pre-computation

We can precompute which substrings are palindromes using DP, reducing the palindrome check to O(1):

def partition_optimized(s: str) -> list:
    """Palindrome partitioning with DP-precomputed palindrome checks."""
    n = len(s)
    # Precompute palindrome table
    is_pal = [[False] * n for _ in range(n)]
    for i in range(n):
        is_pal[i][i] = True
    for i in range(n - 1):
        is_pal[i][i + 1] = (s[i] == s[i + 1])
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            is_pal[i][j] = (s[i] == s[j]) and is_pal[i + 1][j - 1]

    result = []

    def backtrack(start: int, path: list):
        if start == n:
            result.append(path[:])
            return
        for end in range(start, n):
            if is_pal[start][end]:
                path.append(s[start:end + 1])
                backtrack(end + 1, path)
                path.pop()

    backtrack(0, [])
    return result

Palindrome Partitioning II — Minimum cuts (LeetCode 132)

Find the minimum number of cuts needed so every piece is a palindrome. This is a pure DP problem:

def min_cut(s: str) -> int:
    """Minimum cuts for palindrome partitioning. O(n²) time and space."""
    n = len(s)

    # Precompute palindrome table
    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

    # dp[i] = minimum cuts for s[0:i+1]
    dp = list(range(n))  # Worst case: cut every character

    for i in range(1, n):
        if is_pal[0][i]:
            dp[i] = 0  # Whole prefix is a palindrome
            continue
        for j in range(1, i + 1):
            if is_pal[j][i]:
                dp[i] = min(dp[i], dp[j - 1] + 1)

    return dp[n - 1]

Time complexity: O(n²) — we fill two n x n tables. Space complexity: O(n²) — for the palindrome table.

5. Palindromic subsequences

Longest palindromic subsequence (LeetCode 516)

Unlike substrings, subsequences don’t need to be contiguous. This is a classic DP problem closely related to Longest Common Subsequence (LCS):

def longest_palindromic_subsequence(s: str) -> int:
    """Length of the longest palindromic subsequence. O(n²) time and space."""
    n = len(s)
    # dp[i][j] = length of longest palindromic subsequence in s[i:j+1]
    dp = [[0] * n for _ in range(n)]

    # Every single character is a palindrome of length 1
    for i in range(n):
        dp[i][i] = 1

    # Fill for increasing lengths
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

    return dp[0][n - 1]

Key insight: If the first and last characters match, they’re part of the palindrome and we recurse on the inner portion. If they don’t, we take the best of excluding either end.

Big-O summary

Problem	Time	Space
Check palindrome	O(n)	O(1)
Longest palindromic substring (expand)	O(n²)	O(1)
Longest palindromic substring (Manacher)	O(n)	O(n)
Count palindromic substrings	O(n²)	O(1)
Palindrome partitioning I	O(n · 2^n)	O(n²)
Palindrome partitioning II (min cuts)	O(n²)	O(n²)
Longest palindromic subsequence	O(n²)	O(n²)

Practice problems

Work through these in order to solidify the patterns:

1. Valid Palindrome (LeetCode 125) — Basic two-pointer check with cleanup
2. Valid Palindrome II (LeetCode 680) — Remove at most one character
3. Longest Palindromic Substring (LeetCode 5) — Expand around center
4. Palindromic Substrings (LeetCode 647) — Count all palindromes
5. Palindrome Partitioning (LeetCode 131) — Backtracking
6. Palindrome Partitioning II (LeetCode 132) — Minimum cuts DP
7. Longest Palindromic Subsequence (LeetCode 516) — 2D DP
8. Palindrome Pairs (LeetCode 336) — Hash map + palindrome checks
9. Shortest Palindrome (LeetCode 214) — KMP-based approach

Key takeaways

• Two pointers are your go-to for simple palindrome checks — O(n) time, O(1) space.
• Expand around center handles most substring palindrome problems in O(n²) and is easy to implement under pressure.
• Manacher’s algorithm brings it down to O(n) but is rarely required — know it exists, and be ready to explain the mirror property.
• DP pre-computation of palindrome substrings speeds up partitioning and counting problems by making palindrome checks O(1).
• Palindromic subsequence problems reduce to LCS-style DP — the recurrence depends on whether endpoints match.