Solution For Palindromic Substrings
Problem Description:
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 substrings: “a”, “a”, “a”, “aa”, “aa”, “aaa”.
Approach:
The solution to this problem can be achieved using Dynamic Programming. For a string to be palindromic, it should have 1 or 2 characters repeating at the beginning and end of each subproblem. We can use a two-dimensional boolean array to keep track of the subproblems. So, if we have a palindromic substring substring(i, j), then substring(i+1, j-1) should also be a palindromic substring if the characters at position i and j are equal.
Algorithm:
- Initialize a two-dimensional boolean array dp of size n x n, where n is the length of the string s.
- Initialize a count variable to 0.
- Traverse the string s from the end and for each index i:
a. Traverse the string s from i to the end and for each index j:
i. If i and j are equal, set the value of dp[i][j] to True
ii. If the value of dp[i][j] is True, increase the count by 1. - Return the count.
Code:
public int countSubstrings(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
int count = 0;
for(int i=n-1; i>=0; i--){
for(int j=i; j<n; j++){
if(s.charAt(i) == s.charAt(j)){
if(j-i+1 <= 2)
dp[i][j] = true;
else
dp[i][j] = dp[i+1][j-1];
}
if(dp[i][j])
count++;
}
}
return count;
}
Time Complexity: O(n^2)
Space Complexity: O(n^2)
Step by Step Implementation For Palindromic Substrings
public class Solution { public int countSubstrings(String s) { int n = s.length(); int res = 0; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { if (isPalindrome(s, i, j)) { res++; } } } return res; } private boolean isPalindrome(String s, int i, int j) { while (i < j) { if (s.charAt(i++) != s.charAt(j--)) { return false; } } return true; } }
class Solution(object): def countSubstrings(self, s): """ :type s: str :rtype: int """ # Solution: # We can solve this problem by keeping track of the number of # palindromic substrings as we iterate through the string. # We can do this by maintaining a 2D boolean array, where # dp[i][j] is true if the substring s[i:j+1] is a palindrome. # We can then compute the number of palindromic substrings by # summing up the number of dp[i][j] that are true. # The base cases are when i == j, which is always a palindrome, # and when i == j - 1. If s[i] == s[j], then it's a palindrome # if dp[i+1][j-1] is a palindrome. Otherwise, it's not a palindrome. # We can then fill in the rest of the dp array in a bottom-up fashion. # Time Complexity: O(n^2) # Space Complexity: O(n^2) # Initialize 2D boolean array n = len(s) dp = [[False] * n for _ in range(n)] # Base cases for i in range(n): dp[i][i] = True for i in range(n-1): dp[i][i+1] = s[i] == s[i+1] # Fill in rest of array in bottom-up fashion for j in range(2, n): for i in range(0, j-1): dp[i][j] = s[i] == s[j] and dp[i+1][j-1] # Sum up number of dp[i][j] that are true count = 0 for i in range(n): for j in range(n): if dp[i][j]: count += 1 return count
var countSubstrings = function(s) { let n = s.length, ans = 0; for (let i = 0; i < 2 * n - 1; ++i) { let l = i / 2, r = i / 2 + i % 2; while (l >= 0 && r < n && s[l] == s[r]) { --l; ++r; ++ans; } } return ans; };
class Solution { public: int countSubstrings(string s) { int n = s.length(); int ans = 0; for(int i = 0; i < n; i++) { for(int j = i; j < n; j++) { if(isPalindrome(s.substr(i, j-i+1))) { ans++; } } } return ans; } bool isPalindrome(string s) { int n = s.length(); for(int i = 0; i < n/2; i++) { if(s[i] != s[n-1-i]) { return false; } } return true; } };
public class Solution { public int CountSubstrings(string s) { int count = 0; for (int i = 0; i < s.Length; i++) { //odd length count += ExpandFromMiddle(s, i, i); //even length count += ExpandFromMiddle(s, i, i + 1); } return count; } private int ExpandFromMiddle(string s, int left, int right) { int count = 0; while (left >= 0 && right < s.Length && s[left] == s[right]) { count++; left--; right++; } return count; } }