Palindromic Substrings
You have been given a string STR. Your task is to find the total number of palindromic substrings of STR.
Example :
If the input string is "abbc", then all the possible palindromic substrings would be: ["a", "b", "b", c", "bb"] and hence, the output will be 5 since we have 5 substrings in total which form a palindrome.
Note :
A string is said to be a 'Palindrome' if it is read the same forwards and backwards.
For example, “abba” is a palindrome, but “abbc” is not.
A 'Substring' is a contiguous sequence of characters within a string.
For example, "a", "b", "c", "ab", "bc", "abc" are substrings of "abc".
Input format :
The first line contains an integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow.
The first and only line of each test case contains the string STR for which you have to count the number of palindromic substrings.
Output Format :
For each test case, return the total number of palindromic substrings possible.
Output for each test case will be printed in a separate line.
Note
You are not required to print anything, it has already been taken care of. Just implement the function.
Constraints :
1 <= t <= 100
0 <= N <= 1000
Where 't' is the number of test cases, 'N' is the length of the given string.
Time Limit: 1 sec.
- Initialize a count variable with 0 to keep track of the number of palindromic substrings.
- Let n be the length of the input string. Run a double nested loop. The outer loop will go from i = 0 to i = n - 1, and the inner loop will go from j = i to j = n - 1. i and j denote the start and end indices of a substring in the input string.
- Check whether the substring from index i to j forms a palindrome.
- If it does, increase the count by 1 and move to the next iteration.
- If it doesn't, move to the next iteration.
- Return the count.
The idea is to solve recursively or to put in other words, we are going to break the problem into smaller subproblems and take the decision on the basis of the solutions of these small subproblems.
Let's take a look at the recurrence relation for this problem:
First, let our string, str, be defined as
str = <str[0] str[1] str[2] … str[n - 1]>where str[i] is the i'th character of the string and n is the length of the string. Let str(i, j) be defined as the substring of str from index i to index j and let F(i, j) be the number of palindromic substrings in str(i, j)
Now the recurrence relation to find F(i, j) if str(i, j) is not a palindrome will be:
F(i, j) = F(i+1, j) + F(i, j-1) - F(i+1, j-1)And if str(i, j) is a palindrome, the relation will be:
F(i, j) = F(i+1, j) + F(i, j-1) - F(i+1, j-1) + 1We solve the smallest subproblems which are going to be the base cases or the end points of the recursive calls.
Idea is to compare the first and last characters of the string and see if we can deduce some result from it.
1. Let's say, we have startIndex and endIndex pointing at the first and last characters. If these indices cross each other then it essentially means, there are no characters to look at and hence the answer would be straight forward. The count of the number of palindromic substrings possible for this case would certainly be 0 and wont be a palindrome either. Hence, we will return two informations,
i. Total number of substrings possible, and
ii. Whether the string that we are looking at is a palindrome or not?
2. Character of 1 length, it is certainly a palindrome and the total number of palindromic substring possible is 1 since a string of length 1 is a substring itself and a palindrome either.
3. String of length 2, if both the characters are equal then it certainly is a palindrome and the total number of possible palindromic substring would be 3, that is, the two characters and the string itself.
4. At this point we have handled all the two base cases and 1 special case.
5. Here we make 3 calls in order to explore all the possibilities.
i. Including the first character and leaving the last one
ii. Excluding the first and including the last
iii. Excluding both the first and the last characters
6. We sum up the results of the first 2 calls and subtract the result of the third call since it we would have the count of redundant palindromic substrings and we want to get rid of them
7. At this point we have explored all the possibilities and have the answer. 1 last possibility that we need to consider is when the first and last characters are same given that the string in between is itself a palindrome and we have this info with every recursive call along with the number of palindromic substring it can produce.
In this case, the whole string will be a palindrome and we incorporate this to our ans by adding 1 and marking the whole string as true for being a palindrome. else we return the ans we computed at step-6 by marking the string false for not being a palindrome.
Let's take a look at the recurrence relation for this problem:
First, let our string, str, be defined as
str = <str[0] str[1] str[2] … str[n - 1]>where str[i] is the i'th character of the string and n is the length of the string. Let str(i, j) be defined as the substring of str from index i to index j and let F(i, j) be the number of palindromic substrings in str(i, j)
Now the recurrence relation to find F(i, j) if str(i, j) is not a palindrome will be:
F(i, j) = F(i+1, j) + F(i, j-1) - F(i+1, j-1)And if str(i, j) is a palindrome, the relation will be:
F(i, j) = F(i+1, j) + F(i, j-1) - F(i+1, j-1) + 1- Make a boolean 2D array of size n x n, dp, where dp[i][j] will store true if str(i, j) is palindromic, false otherwise.
- Initialize a count variable with 0 to keep track of the number of palindromic substrings.
- First set the value of all dp[i][i] where i goes from 0 to n - 1 as true since single character strings are palindromic. Also, increase the count by 1 for each i.
- Then check for all 2 length substrings by checking if str[i] == str[i + 1] for all i from i = 0 to i = n - 2. Set the value of dp[i][i + 1] and increase the value of count accordingly
- Finally we will check for palindromes for substrings of length 3 to n.
- dp[i][j] will be true if and only if dp[i + 1][j - 1] is true AND str[i] == str[j].
- So for all i and j where j - i + 1 ≥ 3, we will check the above condition. If it's satisfied, we will increase count by 1.
- Return the count.
First, we consider the case of odd length substrings and check for palindromes.
We keep a global count initialized with 0.
1. Iterate over each character of the string
2. Consider the character to be the centre of the palindrome. We can add 1 to the global count since every character is palindrome.
3. Now we start picking 2 characters at once, one from the left and another from the right of the current character that we are looking at. We check if these two characters are equal. If they are, we add 1 to the global count since the string formed after expanding over both the sides are again a palindrome. if not, we break and move to step 2.
Now we consider the case when the substrings are even:
1. Iterate over each character again.
2. This time, consider a substring of length 2 to begin with. We take one more character ahead of the curr character and see if they together make a palindrome or not. If they do, add 1 to the global count and expand it towards the left and right as we did earlier. If they form a palindrome again, keep on increasing the count and if they don't at any point, move to step 1.
Return the global count finally.
