Palindromic Substrings Leetcode Solution

Difficulty Level Medium
Frequently asked in Amazon Apple Bloomberg Facebook Google Microsoft Salesforce Twitter
Dynamic Programming StringViews 2765

Problem Statement

The Palindromic Substrings LeetCode Solution – “Palindromic Substrings” asks you to find a total number of palindromic substrings in the input string.

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:

Input:  s = "aaa"
Output: 6

Explanation:

  • All substrings are: [a,a,a,aa,aa,aaa].
  • All the above substrings are palindrome, hence the answer is 6.
Input:  s = "abc"
Output: 3

Explanation:

  • All substrings are: [a,b,c,ab,bc,abc].
  • Palindromic substrings are: [a,b,c]. Hence the answer is 3.

Approach

Idea:

  1. The main idea to solve this problem is to use dynamic programming.
  2. Maintain a boolean 2D vector that stores whether the substring [i:j] is a palindrome or not.
  3. We’ll iterate for smaller-length substrings then move on to higher-length substrings.
  4. dynamic programming relation is given by: dp[i][j]=true if s[i]==s[j] and dp[i+1][j-1]==true.
  5. After filling the boolean matrix, we’ll iterate for all the substrings and increment our answer by 1 if the substring is a palindrome.

Code for Palindromic Substrings Leetcode Solution:

C++ Solution:

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.length();
        vector<vector<bool>> dp(n,vector<bool>(n));
        for(int i=0;i<n;i++){
            dp[i][i] = true;
        }
        for(int L=2;L<=n;L++){
            for(int i=0;i+L<=n;i++){
                int j = i + L - 1;
                if(L==2){
                    dp[i][j] = s[i]==s[j];
                }
                else if(s[i]==s[j] and dp[i+1][j-1]){
                    dp[i][j] = true;
                }
            }
        }
        int ans = 0;
        for(int i=0;i<n;i++){
            for(int j=i;j<n;j++){
                ans += dp[i][j];
            }
        }
        return ans;
    }
};

Java Solution:

class Solution {
    public int countSubstrings(String s) {
        int n = s.length(),res = 0;
        boolean[][] dp = new boolean[n][n];
        for(int i=0;i<n;i++){
            dp[i][i] = true;
        }
        for(int L=2;L<=n;L++){
            for(int i=0;i+L<=n;i++){
                int j = i + L - 1;
                if(L==2){
                    dp[i][j] = s.charAt(i)==s.charAt(j);
                }
                else if(s.charAt(i)==s.charAt(j) && dp[i+1][j-1]){
                    dp[i][j] = true;
                }
            }
        }
        int ans = 0;
        for(int i=0;i<n;i++){
            for(int j=i;j<n;j++){
                if(dp[i][j]){
                    ans++;
                }
            }
        }
        return ans;
    }
}

Complexity Analysis for Palindromic Substrings Leetcode Solution

Time Complexity

The time complexity of the above code is O(N^2) since we traverse for every substring which takes O(N^2) time.

Space Complexity

The space complexity of the above code is O(N^2). A 2D vector of size N*N has been made to store answers for every substring.

Reference: https://en.wikipedia.org/wiki/Palindrome

Translate »