Leetcode 647 Palindromic Substrings (Medium)

Subscribe to my newsletter and never miss my upcoming articles

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/v162895..)

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;
    }
}
 
Share this