grid47 Exploring patterns and algorithms
Sep 3, 2024
5 min read
Solution to LeetCode 647: Palindromic Substrings Problem
Given a string s, return the number of palindromic substrings in it. A palindrome is a string that reads the same forward and backward. A substring is a contiguous sequence of characters within the string.
Problem
Approach
Steps
Complexity
Input: The input consists of a string s, which contains lowercase English letters.
Example: s = "abc"
Constraints:
• 1 <= s.length <= 1000
• s consists of lowercase English letters.
Output: Return the number of palindromic substrings in the given string s.
Example: 3
Constraints:
• The result will be a single integer representing the count of palindromic substrings.
Goal: Count the number of palindromic substrings in the string.
Steps:
• 1. Initialize a dynamic programming (DP) table to store whether a substring is a palindrome.
• 2. Iterate over all possible substrings and use the DP table to check if they are palindromes.
• 3. Count the palindromes by summing up the number of valid palindromic substrings.
Goal: The string s will always consist of lowercase English letters.
Steps:
• 1 <= s.length <= 1000
• s contains only lowercase English letters.
Assumptions:
• The string is not empty.
• The solution must handle strings up to length 1000 efficiently.
• Input: s = "abc"
• Explanation: The palindromic substrings are: 'a', 'b', 'c'. Hence, the total count is 3.
Approach: The approach uses dynamic programming (DP) to efficiently count all palindromic substrings by building up from smaller substrings.
Observations:
• A palindrome substring must have the same first and last characters, and the substring excluding the first and last characters must also be a palindrome.
• By using dynamic programming, we can efficiently keep track of which substrings are palindromes and count them.
Steps:
• 1. Initialize a DP table where dp[i][j] represents whether the substring s[i..j] is a palindrome.
• 2. For each possible substring, check if it can form a palindrome (i.e., the first and last characters are the same, and the substring excluding those characters is a palindrome).
• 3. Count each valid palindromic substring.
Empty Inputs:
• The input string will always have at least one character.
Large Inputs:
• Ensure that the solution can handle strings of length up to 1000 efficiently.
Special Values:
• Consider strings where all characters are the same or strings with no palindromic substrings.
Constraints:
• Efficiently handle large inputs with a time complexity of O(n^2).
vector<vector<int>> mem;
string s;
intdp(int i, int j) {
if(i >= j) return1;
if(mem[i][j] !=-1) return mem[i][j];
return mem[i][j] = (s[i] == s[j])? dp(i +1, j -1):0;
}
intcountSubstrings(string s) {
this->s = s;
int n = s.size();
mem.resize(n, vector<int>(n, -1));
int ans =0;
for(int i =0; i < s.size(); i++)
for(int j = i; j < s.size(); j++)
ans += dp(i, j);
return ans;
}
1 : Variable Initialization
vector<vector<int>> mem;
Declares a 2D vector 'mem' to store the results of subproblems for memoization. This will be used to avoid redundant calculations of the palindrome checks.
2 : Variable Initialization
string s;
Declares a string 's' to store the input string for which the number of palindromic substrings will be counted.
3 : Recursive Function Definition
intdp(int i, int j) {
Defines the recursive function 'dp' that checks whether the substring from index 'i' to 'j' is a palindrome. It returns 1 if the substring is a palindrome, otherwise 0.
4 : Base Case
if(i >= j) return1;
Checks if the substring length is 1 or 0 (i.e., i >= j), in which case it is a palindrome by definition, so it returns 1.
5 : Memoization Check
if(mem[i][j] !=-1) return mem[i][j];
Checks if the result for the substring from 'i' to 'j' has already been computed (stored in 'mem'). If it has, it returns the stored result.
Recursively checks if the substring is a palindrome. If the characters at positions 'i' and 'j' are equal, it calls 'dp' on the next inner substring. If not, it returns 0.
7 : Function Definition
intcountSubstrings(string s) {
Defines the main function 'countSubstrings' which takes the string 's' and returns the total number of palindromic substrings.
8 : Input Assignment
this->s = s;
Assigns the input string 's' to the class member variable 's'.
9 : Variable Initialization
int n = s.size();
Stores the size of the string 's' in the variable 'n'.
10 : Memoization Setup
mem.resize(n, vector<int>(n, -1));
Resizes the 'mem' vector to a 2D array of size n x n, initializing all values to -1. This will be used to store results of the 'dp' function.
11 : Result Initialization
int ans =0;
Initializes the variable 'ans' to 0, which will store the total count of palindromic substrings.
12 : Outer Loop
for(int i =0; i < s.size(); i++)
Starts an outer loop to iterate through each character of the string 's'.
13 : Inner Loop
for(int j = i; j < s.size(); j++)
Starts an inner loop to consider all substrings starting at index 'i' and ending at index 'j'.
14 : Counting Palindromes
ans += dp(i, j);
Calls the 'dp' function to check if the substring from 'i' to 'j' is a palindrome. Adds the result (1 or 0) to 'ans'.
15 : Final Return
return ans;
Returns the final count of palindromic substrings stored in 'ans'.
Best Case: O(n^2)
Average Case: O(n^2)
Worst Case: O(n^2)
Description: The time complexity is O(n^2) due to the nested loops used to check each substring.
Best Case: O(n^2)
Worst Case: O(n^2)
Description: The space complexity is O(n^2) due to the DP table storing results for all substrings.
