Leetcode 647 Palindromic Substrings (Medium)

647. Palindromic Substrings -Leetcode

Question

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

Example 1:

Input: s = "abc" Output: 3 Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: s = "aaa" Output: 6 Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Constraints:

1 <= s.length <= 1000
s consists of lowercase English letters.

Intution

Any String which is of a single character is a palindrome i.e. a,b,c,d,e etc all are palindrome.
For a string of 2 character it is a palindrome if both characters are same i.e. 0th and 1st character are same. aa,bb,cc,dd etc are palindrome but ab,ba,cf are not palindrome

Any String of more than 3 characters are palindrome if the first and last character are same and the Substrings within first and last character is a palindrome.
Implementation
Let us represent String in a matrix of n x n , where n is the length of the matrix. For example if we take the string as "abcba" we will create a matrix of nxn . In this matrix rows represent starting position and column will represent the ending position of the substring. Below pics tell walk us step by step to approach used in intution

Number of pallindrome substring.jpg

Number of pallindrome substring (1).jpg

Number of pallindrome substring (2).jpg

Number of pallindrome substring (3).jpg

Number of pallindrome substring (4).jpg

Number of pallindrome substring (5).jpg

Number of pallindrome substring (6).jpg hnode.com/res/hashnode/image/upload/v1628953434477/mJeyDfunW.jpeg)

Number of pallindrome substring (7).jpg

Code in Java

Let us look at actual code implementation of the solution

class Solution {
    public int countSubstrings(String s) {
        int m = s.length();
        int n = m;
        int count = 0;
        boolean[][] p = new boolean[m][n];
        for (int k = 0; k < n; k++) {
            int i = 0;
            int j = k;
            while (i < m && j < n) {
                if (i == j) {
                    p[i][j] = true;
                } else if (j - i == 1 && s.charAt(i) == s.charAt(j)) {
                    p[i][j] = true;
                } else if (s.charAt(i) == s.charAt(j) && p[i + 1][j - 1])
                    p[i][j] = true;
                if (p[i][j])
                    count++;
                i++;
                j++;
            }
        }

        return count;
    }
}

Leetcode 647 Palindromic Substrings (Medium)

Comments

More from this blog

Spring AI Tool Calling: From Chatbot to AI Agent with @Tool

Spring AI Advisors API in Java: Build Middleware for AI Interactions

Working with Multiple AI Models in Spring AI — @Qualifier, mutate(), and Model Routing

Spring AI ChatClient API: The Fluent Heart of AI Integration

What is Spring AI? — Why Java Developers Need This in 2026

647. Palindromic Substrings -Leetcode

Question

Intution

Implementation

Code in Java

Command Palette

Comments

More from this blog

647. Palindromic Substrings -Leetcode

Question

Intution

Implementation

Code in Java