Data Structures & Algorithms in Java – Strings – Palindromic substrings

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:

https://fullstackdeveloper.guru/2022/08/29/data-structures-algorithms-in-java-strings-longest-palindromic-substring/

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!