Problem:
Given a string , find the number of palindromic substrings in the string.
For example , for the input “babad” the number of palindromic substrings is 7:
“b” , “a”, “b”,”a”,”d” , “aba” , “bab”
Try out the solution here:
https://leetcode.com/problems/palindromic-substrings/
Solution:
The solution is almost the same as we discussed in the previous post:
The only difference is instead of finding the length of the maximum window and its start position we increment a count variable each time we find a palindrome.
Here is the modified code:
class Solution {
int no = 0;
public int countSubstrings(String s) {
if(s.length() == 1) return 1;
char[] array = s.toCharArray();
for(int i=0;i<s.length();i++){
check(array,i,i);
check(array,i,i+1);
}
return no;
}
void check(char[] a,int i,int j){
while(i>=0 && j < a.length && a[i] == a[j]){
i--;
j++;
no++;
}
}
}
As you see everytime a palindrome is found out the count is incremented.
That’s it!
Leave a Reply