DEV Community

Vishal Bharadwaj
Vishal Bharadwaj

Posted on

1 1

Palindromic Substrings

class Solution {
    public int countSubstrings(String s) {
        int count=0;
        for(int i=0;i<s.length();i++){
            count+=expand(s,i,i);//palindromes of the form WCW'
            count+=expand(s,i,i+1);//palindromes of the form WW'
        }
        return count;
    }
    private int expand(String s,int start,int end){

        int len=0;
        while(start>=0 && end<s.length() && s.charAt(start)==s.charAt(end)){
            len++;
            start--;
            end++;
        }
        return len;
    }
}
Enter fullscreen mode Exit fullscreen mode

There are basically two types of palindromes, odd length and even length.
Odd length palindromes are of the form WCW'
for example, DAD, MOM, RACECAR. In all of these examples there's one character that separates the equivalent characters around it. To satisfy this condition we compare the character to itself and then go on expanding around it as the code shows. This is also the case of single characters where the character itself is a palindrome considering the Ws on both sides to be null.
W' being the reverse of W.

On the other hand, for even palindromic strings like bb, aa, you directly compare it with the character right next to it. If it is a palindrome the characters match and you move forwards in W' and backwards in W thereby comparing the characters at the same position but in reverse.

Image of Datadog

How to Diagram Your Cloud Architecture

Cloud architecture diagrams provide critical visibility into the resources in your environment and how they’re connected. In our latest eBook, AWS Solution Architects Jason Mimick and James Wenzel walk through best practices on how to build effective and professional diagrams.

Download the Free eBook

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs