Problem
You are given a strings. Return the number of palindromic substrings in s.
A substring is a palindrome if it reads the same forward and backward. Different occurrences of the same substring are counted separately.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
s = "aaa"Output
6Solution
A palindrome can have either an odd-length center or an even-length center.For an odd-length palindrome, the center is a character. For example,
"aba" expands from the middle character 'b'.
For an even-length palindrome, the center lies between two characters. For example,
"abba" expands from the two middle characters 'b' and 'b'.
We treat every character as the center of an odd-length palindrome and every gap between two characters as the center of an even-length palindrome.
From each center, we expand in both directions while the characters are equal. Every successful expansion represents one palindromic substring.
class Solution {
public int countSubstrings(String s) {
int count = 0;
for (int i = 0; i < s.length(); i++) {
// Odd-length palindromes.
count += expand(s, i, i);
// Even-length palindromes.
count += expand(s, i, i + 1);
}
return count;
}
private int expand(String s, int left, int right) {
int count = 0;
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
// Found a palindrome.
count++;
// Expand around the center.
left--;
right++;
}
return count;
}
}
Complexity
There are2n - 1 possible centers, and expanding from each center can take up to O(n) time. Therefore, the overall time complexity is O(nĀ²).
Only a constant number of variables is used apart from the input string, so the space complexity is
O(1).
Dynamic Programming Approach
This problem can also be solved using Dynamic Programming.Let
dp[i][j] represent whether the substring from index i to j is a palindrome.
A substring is a palindrome when its first and last characters are equal, and the substring between them is also a palindrome.
The condition
j - i < 2 handles substrings with one or two characters.
Whenever a substring is identified as a palindrome, we increment the count.
class Solution {
public int countSubstrings(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
int count = 0;
for (int left = n - 1; left >= 0; left--) {
for (int right = left; right < n; right++) {
if (s.charAt(left) == s.charAt(right)
&& (right - left < 2 || dp[left + 1][right - 1])) {
// Found a palindromic substring.
dp[left][right] = true;
count++;
}
}
}
return count;
}
}
Complexity
The DP table checks every possible substring, resulting inO(nĀ²) time complexity. The n Ć n DP table requires O(nĀ²) space.