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

hnode.com/res/hashnode/image/upload/v1628953434477/mJeyDfunW.jpeg)

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