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/
Advertisements
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!