☕ DSA Java Articles

Topics › Strings › Medium String Problems

Palindromic Substrings

Medium TUF ID 2794 Blind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given a string s, return how many of its substrings are palindromes. A substring is a contiguous, non-empty block of characters, and substrings at different positions count separately even when their text is the same.

Constraints: 1 ≤ n ≤ 1000, lowercase English letters. The Java methods also accept the empty string, which has 0 palindromic substrings.

Example 1

s = "abc"
answer = 3          // "a", "b", "c"; no longer substring reads the same backwards

Example 2

s = "aaa"
answer = 6          // "a" three times, "aa" twice (positions 0-1 and 1-2), "aaa" once

Every single character is a palindrome, so the answer is always at least n. At the other extreme, a string of one repeated letter makes every substring a palindrome, giving n(n+1)/2.

Approach 1: Brute force, check every substring

Intuition. Enumerate all n(n+1)/2 substrings by start i and end j, and test each one with two pointers that move inward from both ends. Count the ones that pass.

Algorithm.

  1. For every i and every j ≥ i:
  2. Compare s[lo] with s[hi] for lo = i, hi = j, moving inward until the pointers meet or a mismatch is found.
  3. If no mismatch was found, increment the count.
static int bruteForce(String s) {
    int n = s.length(), count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if (isPalindrome(s, i, j)) count++;
        }
    }
    return count;
}

static boolean isPalindrome(String s, int lo, int hi) {
    while (lo < hi) {
        if (s.charAt(lo++) != s.charAt(hi--)) return false;
    }
    return true;
}

Complexity. Time O(n^3): O(n^2) substrings, each tested in up to n/2 comparisons. On "aaa...a" every test runs to completion, about n^3/12 comparisons, roughly 8 × 10^7 for n = 1000. Space O(1).

That may squeeze through for n = 1000, but it repeats work everywhere. Testing s[1..7] compares s[2] with s[6] and s[3] with s[5], which is exactly the test for s[2..6] that was already done.

Approach 2: Better, DP table of palindromic ranges

Intuition. A range is a palindrome when its two ends match and the range just inside them is a palindrome:

pal[i][j] = (s[i] == s[j]) && (j - i < 2 || pal[i+1][j-1])

Ranges of length 1 and 2 have no meaningful inside, so only the end characters matter (and for length 1, i == j, they trivially match). Each cell needs only the cell diagonally down-left of it, pal[i+1][j-1]. If we fill rows from the bottom (i from n - 1 down to 0), row i + 1 is complete before row i starts, so that cell is always ready. Every true cell is one palindromic substring, so we count them as we go.

Algorithm.

  1. For i = n - 1 down to 0, for j = i to n - 1:
  2. Set pal[i][j] using the recurrence above.
  3. If it is true, increment the count.
static int better(String s) {
    int n = s.length(), count = 0;
    boolean[][] pal = new boolean[n][n];
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            pal[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || pal[i + 1][j - 1]);
            if (pal[i][j]) count++;
        }
    }
    return count;
}

Complexity. Time O(n^2): each cell is O(1). Space O(n^2) booleans, about a megabyte for n = 1000.

The table is worth keeping in mind because other problems need it as a lookup, for example Palindrome partitioning asks “is s[i..j] a palindrome?” many times. For a pure count, though, each cell is read once and then forgotten, which hints that the table is unnecessary.

Approach 3: Optimal, expand around every centre

Intuition. Look at the DP from the point of view of a single palindrome. pal[i][j] depends on pal[i+1][j-1], which depends on pal[i+2][j-2], and so on toward the middle. All palindromes that share a middle form a chain, and walking that chain outward is just “expand from the centre while the two ends match”.

A palindrome’s centre is either a character (odd length) or the gap between two characters (even length), so there are n + (n - 1) = 2n - 1 centres. From one centre, the palindromes are nested: once a window fails, every wider window around the same centre also fails, because it contains the same mismatched pair. Therefore the number of palindromes around a centre equals the number of successful expansion steps before the first failure.

Nothing is counted twice: each palindromic substring has exactly one centre (its midpoint) and one length, so it is found once, at its own centre, at its own step.

Algorithm.

  1. For each index c, add countFrom(c, c) (odd) and countFrom(c, c + 1) (even).
  2. countFrom(lo, hi) increments found and widens the window while lo and hi are in range and s[lo] == s[hi].
  3. Return the total.
static int optimal(String s) {
    int count = 0;
    for (int c = 0; c < s.length(); c++) {
        count += countFrom(s, c, c);            // odd lengths, centred on s[c]
        count += countFrom(s, c, c + 1);        // even lengths, centred between s[c] and s[c+1]
    }
    return count;
}

/** Each successful expansion step uncovers exactly one new palindrome around this centre. */
static int countFrom(String s, int lo, int hi) {
    int found = 0;
    while (lo >= 0 && hi < s.length() && s.charAt(lo) == s.charAt(hi)) {
        found++;
        lo--;
        hi++;
    }
    return found;
}

Dry run on s = "aaa":

c odd windows found even windows found running total
0 [0,0] → 1 [0,1] → 1 2
1 [1,1], [0,2] → 2 [1,2] → 1 5
2 [2,2] → 1 none (no index 3) → 0 6

Complexity. Time O(n^2) in the worst case (the all-equal string expands as far as possible from every centre), but only O(n + P) in general, where P is the answer itself: each loop iteration either finds a palindrome or stops. Space O(1).

That second bound is a nice way to see why this approach is the natural optimum for a counting problem: we cannot do less than one step per palindrome if we enumerate them, and this method does exactly that plus O(1) per centre.

Going linear

If n were 10^6, even O(n + P) could be too slow, since P can be about n^2/2. Manacher’s algorithm computes, for every centre, the radius of the longest palindrome around it in O(n) total time. The number of palindromes around a centre is then read off from the radius (in the separator-padded string, a radius r gives (r + 1) / 2 palindromes), and the counts are summed. The radius computation is shown in Longest Palindrome in a string.

Edge cases and pitfalls