875912. Number of Palindromic Substrings
Medium
Number of Palindromic Substrings
Summary
Given a string, find the number of palindromic substrings it contains. A palindromic substring is a contiguous sequence of characters that reads the same backward as forward.
Detailed Explanation
To solve this problem, we'll use a dynamic programming approach to keep track of whether each character and its corresponding substring is a palindrome or not.
Here's the step-by-step breakdown:
- Initialize a 2D boolean array
dpwith dimensions(n x n), wherenis the length of the input string. - Iterate through the string from left to right, considering each character as the center of a potential palindrome.
- For each character, check if the substring starting at that position and ending at the same position (i.e., a single character) is a palindrome. If it is, mark
dp[i][i]astrue. - Then, for each character, consider the substrings of length 2, 3, ..., up to the distance from the center to the end of the string.
- For each such substring, check if it's a palindrome by comparing its characters from both ends. If it is, mark
dp[i][j]astrue, whereiandjare the starting and ending indices of the substring. - Finally, count the number of palindromic substrings by iterating through the
dparray and summing up the values at each position.
Time complexity: O(n^2) Space complexity: O(n^2)
Optimized Solutions
Java
public int numberOfPalindromicSubstrings(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
if (s.charAt(i) == s.charAt(j) && len == 2 || dp[i + 1][j - 1]) {
dp[i][j] = true;
}
}
}
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
if (dp[i][j]) {
count++;
}
}
}
return count;
}