Palindromic Substrings
MedPrompt
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 <= 1000sconsists 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
countto 0. - Generate all possible substrings of the input string
susing two nested loops. The outer loop with indexidetermines the start of the substring, and the inner loop with indexjdetermines the end. - For each substring, create a helper function
isPalindrometo check if it's a palindrome. - The
isPalindromefunction uses two pointers,startandend, 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 thecount. - 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
Solution
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.