Palindromic Substrings

Medium Problem 126 of 151 Java and Python

Problem

Given a string s, return the number of palindromic substrings in it. Substrings at different positions count separately even if they contain the same characters.

Example 1

Input: s = "abc"
Output: 3
Why: "a", "b", "c".

Example 2

Input: s = "aaa"
Output: 6
Why: "a" ×3, "aa" ×2, "aaa".

Constraints

1 ≤ s.length ≤ 1000

Explanation

Same centres as Longest Palindromic Substring. Every successful expansion step from a centre is one more palindrome, so count the steps instead of tracking the longest.

Approach 1 · Naive

Check every substring

Time O(n³)
Space O(1)

Test all O(n²) substrings for being a palindrome.

For every i ≤ j, add 1 if s[i..j] is a palindrome.

Java

class Solution {
    public int countSubstrings(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                int a = i;
                int b = j;
                while (a < b && s.charAt(a) == s.charAt(b)) {
                    a++;
                    b--;
                }
                if (a >= b) {
                    count++;
                }
            }
        }
        return count;
    }
}

Python

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        return sum(1 for i in range(n) for j in range(i, n) if s[i:j + 1] == s[i:j + 1][::-1])

Approach 2 · Optimal

Expand around centres

Time O(n²)
Space O(1)

For each of the 2n - 1 centres, expand while the ends match, counting each step.

For each i, count expansions from (i, i) and from (i, i + 1).
Each step where s[left] == s[right] adds one palindrome.

Java

class Solution {
    public int countSubstrings(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            count += expand(s, i, i) + expand(s, i, i + 1);
        }
        return count;
    }

    private int expand(String s, int left, int right) {
        int found = 0;
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            found++;
            left--;
            right++;
        }
        return found;
    }
}

Python

class Solution:
    def countSubstrings(self, s: str) -> int:
        def expand(left, right):
            found = 0
            while left >= 0 and right < len(s) and s[left] == s[right]:
                found += 1
                left -= 1
                right += 1
            return found

        return sum(expand(i, i) + expand(i, i + 1) for i in range(len(s)))

Complexity compared

Approach	Time	Space
Naive Check every substring	O(n³)	O(1)
Optimal Expand around centres	O(n²)	O(1)

Key takeaways

Once you know expand-around-centre, "longest" and "count" palindrome questions are the same loop.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem