Palindromic Substrings

Description

Given a string s, return the total number of palindromic substrings in it.

A palindrome is a string that reads the same forwards and backwards. For example, "aba" and "aa" are palindromes, while "abc" is not.

A substring is a contiguous sequence of characters within the string. Note that every single character by itself is considered a palindrome, so a string of length n has at least n palindromic substrings.

You need to count all such palindromic substrings, including single characters, pairs of equal adjacent characters, and longer palindromic sequences.

Examples

Example 1

Input: s = "abc"

Output: 3

Explanation: The palindromic substrings are: "a", "b", "c". Each individual character is a palindrome on its own. No multi-character substring is a palindrome because all characters are distinct — "ab", "bc", and "abc" are not palindromes. So the total count is 3.

Example 2

Input: s = "aaa"

Output: 6

Explanation: The palindromic substrings are:

Single characters: "a" (index 0), "a" (index 1), "a" (index 2) → 3 palindromes
Two-character substrings: "aa" (indices 0-1), "aa" (indices 1-2) → 2 palindromes
Three-character substring: "aaa" (indices 0-2) → 1 palindrome

Total: 3 + 2 + 1 = 6. Notice that even though the single-character palindromes have the same value "a", they count separately because they occur at different positions in the string.

Example 3

Input: s = "abba"

Output: 6

Explanation: The palindromic substrings are:

Single characters: "a", "b", "b", "a" → 4 palindromes
Two-character: "bb" (indices 1-2) → 1 palindrome
Four-character: "abba" (indices 0-3) → 1 palindrome
Note: "ab", "ba" are not palindromes. "abb", "bba" are not palindromes.

Total: 4 + 1 + 1 = 6.

Constraints

1 ≤ s.length ≤ 1000
s consists of lowercase English letters only

Editorial

Brute Force

Intuition

The most straightforward way to count palindromic substrings is to examine every possible substring and check whether it is a palindrome.

A string of length n has n × (n + 1) / 2 possible substrings (choosing a start index and an end index). For each substring, we can verify if it is a palindrome by comparing characters from both ends moving inward — if all pairs match, it is a palindrome.

Think of it like reading every possible word in a sentence, and for each word, checking if it spells the same forwards and backwards. You would read it from the left and the right simultaneously, checking letter by letter. This is simple but slow because you end up doing a lot of repetitive checking.

Step-by-Step Explanation

Let's trace through with s = "abc":

Step 1: Initialize count = 0. We will check all substrings.

Step 2: Start with i=0. Check all substrings starting at index 0:

s[0..0] = "a" → single character → palindrome. count = 1.
s[0..1] = "ab" → compare s[0]='a' vs s[1]='b' → 'a' ≠ 'b' → not a palindrome.
s[0..2] = "abc" → compare s[0]='a' vs s[2]='c' → 'a' ≠ 'c' → not a palindrome.

Step 3: Move to i=1. Check substrings starting at index 1:

s[1..1] = "b" → single character → palindrome. count = 2.
s[1..2] = "bc" → compare s[1]='b' vs s[2]='c' → 'b' ≠ 'c' → not a palindrome.

Step 4: Move to i=2. Check substrings starting at index 2:

s[2..2] = "c" → single character → palindrome. count = 3.

Step 5: All substrings checked. Return count = 3.

Brute Force — Checking All Substrings — Watch how we enumerate every possible substring and check each one character-by-character for the palindrome property.

Algorithm

Initialize a counter count = 0
For each starting index i from 0 to n-1:
- For each ending index j from i to n-1:
  - Extract substring s[i..j]
  - Check if it is a palindrome by comparing characters from both ends inward
  - If palindrome, increment count
Return count

Code

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.length();
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (isPalindrome(s, i, j)) {
                    count++;
                }
            }
        }
        
        return count;
    }
    
private:
    bool isPalindrome(const string& s, int left, int right) {
        while (left < right) {
            if (s[left] != s[right]) return false;
            left++;
            right--;
        }
        return true;
    }
};

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        count = 0
        
        for i in range(n):
            for j in range(i, n):
                if self.is_palindrome(s, i, j):
                    count += 1
        
        return count
    
    def is_palindrome(self, s: str, left: int, right: int) -> bool:
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (isPalindrome(s, i, j)) {
                    count++;
                }
            }
        }
        
        return count;
    }
    
    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) return false;
            left++;
            right--;
        }
        return true;
    }
}

Complexity Analysis

Time Complexity: O(n³)

The two nested loops generate O(n²) substrings. For each substring, the palindrome check takes up to O(n) time in the worst case (comparing characters from both ends). This gives a total of O(n²) × O(n) = O(n³).

Space Complexity: O(1)

We only use a few integer variables (count, i, j, left, right). No additional data structures that grow with input size.

Why This Approach Is Not Efficient

The brute force approach is O(n³), which for n = 1000 means up to 10⁹ operations. This will almost certainly exceed time limits.

The fundamental waste is in the palindrome check. When we verify that "abba" is a palindrome, we learn that "bb" (the inner part) is also a palindrome. But in brute force, we check "bb" independently from scratch, ignoring what we already know.

We can exploit the fact that palindromes have a recursive structure: a string is a palindrome if its first and last characters match AND the inner substring is also a palindrome. This leads to a Dynamic Programming approach where we store palindrome results in a table and look them up in O(1) instead of re-checking.

Better Approach - Dynamic Programming

Intuition

Instead of re-checking palindromes from scratch each time, we can build a table that remembers which substrings are palindromes.

We define dp[i][j] = true if the substring s[i..j] is a palindrome. The key recurrence is:

Base case 1: Every single character is a palindrome → dp[i][i] = true
Base case 2: A two-character substring is a palindrome if both characters are the same → dp[i][i+1] = (s[i] == s[i+1])
General case: A longer substring s[i..j] is a palindrome if s[i] == s[j] AND dp[i+1][j-1] is true (the inner substring is a palindrome)

Think of it like building a pyramid of knowledge. At the bottom, you know every single letter is a palindrome. Then you check pairs. Then you use what you know about pairs to check triples, and so on. Each new level of the pyramid builds on the level below it.

We fill the table diagonally — first all substrings of length 1, then length 2, then length 3, etc. Each time dp[i][j] is true, we increment our palindrome count.

Step-by-Step Explanation

Let's trace through with s = "aaa":

Step 1: Initialize dp table of size 3×3 with all false. count = 0.

Step 2: Fill length-1 diagonals (base case). Every character is a palindrome.

dp[0][0] = true ("a"), count = 1
dp[1][1] = true ("a"), count = 2
dp[2][2] = true ("a"), count = 3

Step 3: Fill length-2 substrings.

s[0..1] = "aa": s[0]='a' == s[1]='a' → dp[0][1] = true, count = 4
s[1..2] = "aa": s[1]='a' == s[2]='a' → dp[1][2] = true, count = 5

Step 4: Fill length-3 substrings.

s[0..2] = "aaa": s[0]='a' == s[2]='a' AND dp[1][1] = true (inner "a" is palindrome) → dp[0][2] = true, count = 6

Step 5: All substrings processed. Return count = 6.

DP Table — Filling Palindrome Results Diagonally — Watch how we fill the DP table diagonal by diagonal, starting with single characters, then pairs, then triples. Each cell dp[i][j] tells us whether s[i..j] is a palindrome.

Algorithm

Create a 2D boolean table dp of size n × n, initialized to false
Initialize count = 0
Fill length-1 diagonal: set dp[i][i] = true for all i, increment count for each
Fill length-2 diagonal: for each i, if s[i] == s[i+1], set dp[i][i+1] = true and increment count
Fill remaining diagonals (length 3 to n):
- For each gap from 2 to n-1:
  - For each starting index i where j = i + gap < n:
    - If s[i] == s[j] AND dp[i+1][j-1] is true, set dp[i][j] = true and increment count
Return count

Code

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.length();
        int count = 0;
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        
        // Single characters
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
            count++;
        }
        
        // Two-character substrings
        for (int i = 0; i < n - 1; i++) {
            if (s[i] == s[i + 1]) {
                dp[i][i + 1] = true;
                count++;
            }
        }
        
        // Longer substrings (length 3+)
        for (int len = 3; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                if (s[i] == s[j] && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    count++;
                }
            }
        }
        
        return count;
    }
};

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        count = 0
        dp = [[False] * n for _ in range(n)]
        
        # Single characters
        for i in range(n):
            dp[i][i] = True
            count += 1
        
        # Two-character substrings
        for i in range(n - 1):
            if s[i] == s[i + 1]:
                dp[i][i + 1] = True
                count += 1
        
        # Longer substrings (length 3+)
        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

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        int count = 0;
        boolean[][] dp = new boolean[n][n];
        
        // Single characters
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
            count++;
        }
        
        // Two-character substrings
        for (int i = 0; i < n - 1; i++) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = true;
                count++;
            }
        }
        
        // Longer substrings (length 3+)
        for (int len = 3; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
                    dp[i][j] = true;
                    count++;
                }
            }
        }
        
        return count;
    }
}

Complexity Analysis

Time Complexity: O(n²)

We fill an n × n DP table, but only the upper triangle (where j ≥ i). There are n(n+1)/2 cells total. Each cell is filled in O(1) time since we just check two characters and one precomputed DP value. So the total time is O(n²).

Space Complexity: O(n²)

We use a 2D boolean table of size n × n to store palindrome results. This is the dominant space cost.

Why This Approach Is Not Efficient

The DP approach reduces time from O(n³) to O(n²), which is a significant improvement. However, it uses O(n²) extra space for the DP table. For n = 1000, this means storing 1,000,000 boolean values.

While the time complexity of O(n²) cannot be improved for this problem (since there can be O(n²) palindromic substrings in the worst case, like "aaa...a"), we CAN eliminate the O(n²) space.

The key insight is that instead of checking all pairs (i, j) and asking "is s[i..j] a palindrome?", we can think in terms of palindrome centers. Every palindrome has a center — either a single character (odd-length palindromes like "aba") or a pair of characters (even-length palindromes like "abba"). If we expand outward from each possible center, we find all palindromes centered there. This approach naturally avoids the need for a 2D table.

Optimal Approach - Expand Around Center

Intuition

Every palindrome mirrors around its center. For odd-length palindromes like "racecar", the center is a single character ('e'). For even-length palindromes like "abba", the center is between two characters (between the two 'b's).

Instead of checking every substring, we can iterate through all possible centers and expand outward from each one. Starting at a center, we compare the characters on both sides. As long as they match, we have a palindrome, and we keep expanding. The moment they don't match, we stop — no larger palindrome exists from this center.

Imagine dropping a pebble into a pond. Ripples expand outward from the center. Each ripple that stays symmetric (matching characters on both sides) represents a palindrome. When the ripple hits a mismatch, it stops.

For a string of length n, there are:

n centers for odd-length palindromes (each character)
n-1 centers for even-length palindromes (each pair of adjacent characters)
Total: 2n - 1 centers

From each center, expansion takes at most O(n) time, giving O(n²) total — same as DP, but with O(1) space since we don't need a table.

Step-by-Step Explanation

Let's trace through with s = "aaa":

Step 1: Initialize count = 0. We will try all 2n-1 = 5 centers.

Step 2: Center at index 0 (odd-length). Expand:

left=0, right=0: s[0]='a' → palindrome "a". count = 1.
left=-1, right=1: left < 0, stop.
Found 1 palindrome from this center.

Step 3: Center between index 0 and 1 (even-length). Expand:

left=0, right=1: s[0]='a' == s[1]='a' → palindrome "aa". count = 2.
left=-1, right=2: left < 0, stop.
Found 1 palindrome from this center.

Step 4: Center at index 1 (odd-length). Expand:

left=1, right=1: s[1]='a' → palindrome "a". count = 3.
left=0, right=2: s[0]='a' == s[2]='a' → palindrome "aaa". count = 4.
left=-1, right=3: left < 0, stop.
Found 2 palindromes from this center.

Step 5: Center between index 1 and 2 (even-length). Expand:

left=1, right=2: s[1]='a' == s[2]='a' → palindrome "aa". count = 5.
left=0, right=3: right ≥ n, stop.
Found 1 palindrome from this center.

Step 6: Center at index 2 (odd-length). Expand:

left=2, right=2: s[2]='a' → palindrome "a". count = 6.
left=1, right=3: right ≥ n, stop.
Found 1 palindrome from this center.

Step 7: All 5 centers processed. Return count = 6.

Expand Around Center — Finding All Palindromes — Watch how we place a center at each position, then expand outward as long as characters match. Each successful expansion discovers a new palindromic substring.

Algorithm

Initialize count = 0
For each index i from 0 to n-1:
- Call expandFromCenter(s, i, i) for odd-length palindromes → add result to count
- Call expandFromCenter(s, i, i+1) for even-length palindromes → add result to count
The expandFromCenter(s, left, right) function:
- Initialize palindromes_found = 0
- While left ≥ 0 AND right < n AND s[left] == s[right]:
  - Increment palindromes_found
  - Expand: left--, right++
- Return palindromes_found
Return count

Code

class Solution {
public:
    int countSubstrings(string s) {
        int count = 0;
        int n = s.length();
        
        for (int i = 0; i < n; i++) {
            // Odd-length palindromes centered at i
            count += expandFromCenter(s, i, i);
            // Even-length palindromes centered between i and i+1
            count += expandFromCenter(s, i, i + 1);
        }
        
        return count;
    }
    
private:
    int expandFromCenter(const string& s, int left, int right) {
        int palindromes = 0;
        while (left >= 0 && right < s.length() && s[left] == s[right]) {
            palindromes++;
            left--;
            right++;
        }
        return palindromes;
    }
};

class Solution:
    def countSubstrings(self, s: str) -> int:
        count = 0
        n = len(s)
        
        for i in range(n):
            # Odd-length palindromes centered at i
            count += self.expand_from_center(s, i, i)
            # Even-length palindromes centered between i and i+1
            count += self.expand_from_center(s, i, i + 1)
        
        return count
    
    def expand_from_center(self, s: str, left: int, right: int) -> int:
        palindromes = 0
        while left >= 0 and right < len(s) and s[left] == s[right]:
            palindromes += 1
            left -= 1
            right += 1
        return palindromes

class Solution {
    public int countSubstrings(String s) {
        int count = 0;
        int n = s.length();
        
        for (int i = 0; i < n; i++) {
            // Odd-length palindromes centered at i
            count += expandFromCenter(s, i, i);
            // Even-length palindromes centered between i and i+1
            count += expandFromCenter(s, i, i + 1);
        }
        
        return count;
    }
    
    private int expandFromCenter(String s, int left, int right) {
        int palindromes = 0;
        while (left >= 0 && right < s.length() && 
               s.charAt(left) == s.charAt(right)) {
            palindromes++;
            left--;
            right++;
        }
        return palindromes;
    }
}

Complexity Analysis

Time Complexity: O(n²)

We have 2n - 1 centers (n odd + n-1 even). From each center, the expansion can go at most O(n) steps outward (in the worst case, like "aaa...a" where every expansion reaches the string boundaries). So the total work is (2n - 1) × O(n) = O(n²).

Note: This is the same time complexity as the DP approach. However, the constant factor is smaller because we avoid the overhead of filling a 2D table, and we stop expanding early when characters don't match.

Space Complexity: O(1)

We only use a constant number of variables: count, i, left, right, and palindromes. No arrays, tables, or additional data structures are needed. This is a significant improvement over the O(n²) space of the DP approach.

EASY

MEDIUM

EASY

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

EASY

MEDIUM

HARD

EASY

MEDIUM

HARD

HARD

MEDIUM

MEDIUM

HARD

MEDIUM

HARD

EASY

MEDIUM

MEDIUM

MEDIUM

EASY

MEDIUM

MEDIUM

EASY

MEDIUM

Palindromic Substrings

Description

Examples

Example 1

Example 2

Example 3

Constraints

Editorial

Brute Force

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Better Approach - Dynamic Programming

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis

Why This Approach Is Not Efficient

Optimal Approach - Expand Around Center

Intuition

Step-by-Step Explanation

Algorithm

Code

Complexity Analysis