Scale Engineer

Palindromic Substrings

Med
#0601Time: O(n³), where n is the length of the string. There are O(n²) substrings, and checking if a substring is a palindrome takes O(n) time in the worst case.Space: O(1) extra space, as the palindrome check can be done in-place with pointers without allocating significant new memory.14 companies
Patterns
Two PointersDynamic Programming
Data structures
String
Companies
AccentureBNY MellonCiscoEpic Systems

Prompt

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

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

 

Example 1:

Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

 

Constraints:

  • 1 <= s.length <= 1000
  • s consists of lowercase English letters.

Approaches

4 approaches with complexity analysis and trade-offs.

The most straightforward approach is to generate every possible substring and then, for each one, check if it is a palindrome. If it is, we increment a counter. This method is easy to conceptualize but is the least efficient.

Algorithm

  • Initialize a counter count to 0.
  • Generate all possible substrings of the input string s using two nested loops. The outer loop with index i determines the start of the substring, and the inner loop with index j determines the end.
  • For each substring, create a helper function isPalindrome to check if it's a palindrome.
  • The isPalindrome function uses two pointers, start and end, initialized to the beginning and end of the substring. It checks if characters at these pointers are equal while moving them towards the center.
  • If the helper function returns true, increment the count.
  • After checking all substrings, return the final count.

Walkthrough

This approach iterates through all possible start and end indices to define a substring. For each substring generated, a separate check is performed to determine if it's a palindrome. A simple way to check for a palindrome is to compare the substring with its reverse, or more efficiently, use a two-pointer technique. The outer loops run in O(n²) time to generate all substrings, and the palindrome check for each substring of length k takes O(k) time. In the worst case, this leads to an overall time complexity of O(n³).

class Solution {    public int countSubstrings(String s) {        int count = 0;        int n = s.length();        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 start, int end) {        while (start < end) {            if (s.charAt(start) != s.charAt(end)) {                return false;            }            start++;            end--;        }        return true;    }}

Complexity

Time

O(n³), where n is the length of the string. There are O(n²) substrings, and checking if a substring is a palindrome takes O(n) time in the worst case.

Space

O(1) extra space, as the palindrome check can be done in-place with pointers without allocating significant new memory.

Trade-offs

Pros

  • Simple to understand and implement.

  • Requires minimal extra space.

Cons

  • Very inefficient with a cubic time complexity, making it unsuitable for large inputs.

  • Performs many redundant palindrome checks for overlapping substrings.

Solutions

class Solution { public int countSubstrings ( String s ) { StringBuilder sb = new StringBuilder ( "^#" ); for ( char ch : s . toCharArray ()) { sb . append ( ch ). append ( '#' ); } String t = sb . append ( '$' ). toString (); int n = t . length (); int [] p = new int [ n ]; int pos = 0 , maxRight = 0 ; int ans = 0 ; for ( int i = 1 ; i < n - 1 ; i ++) { p [ i ] = maxRight > i ? Math . min ( maxRight - i , p [ 2 * pos - i ]) : 1 ; while ( t . charAt ( i - p [ i ]) == t . charAt ( i + p [ i ])) { p [ i ]++; } if ( i + p [ i ] > maxRight ) { maxRight = i + p [ i ]; pos = i ; } ans += p [ i ] / 2 ; } return ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem