Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Count of Palindromic Substrings

Problem Statement

Given a string, find the total number of palindromic substrings in it. Please note we need to find the total number of substrings and not subsequences.

Example 1:

Input: "abdbca"
Output: 7
Explanation: Here are the palindromic substrings, "a", "b", "d", "b", "c", "a", "bdb".

Example 2:

Input: = "cddpd"
Output: 7
Explanation: Here are the palindromic substrings, "c", "d", "d", "p", "d", "dd", "dpd".

Example 3:

Input: = "pqr"
Output: 3
Explanation: Here are the palindromic substrings,"p", "q", "r".

Constraints:

  • `1 <= st

.....

.....

.....

Like the course? Get enrolled and start learning!
S

Shan

· 4 years ago

Can you add the brute force, swapping the max for count does not work on the leetcode problem

Show 2 replies
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def findCPS(self, st):
    
    def is_palindrom(s, i, j):
      while i <= j :
        if s[i] != s[j]:
          return False
        i += 1
        j -= 1
      return True

    count = 0
    for i in range(0, len(st)):
      for j in range(i, len(st)):
        if is_palindrom(st, i, j):
            count += 1
    
    return count
Show 1 reply
Vikas Mishra

Vikas Mishra

· a year ago

Generally this question is solved totally different way. using 2 for loops. Is that expected or we can solve this question in similar way as we found longest palindromic substring

A

alik.dudin

· 10 months ago

private int dyn(String st,int startIndex , int endIndex, Integer[][] dp){
    if(startIndex == endIndex){
        return 1;
    }
    if(startIndex>endIndex){
        return 0;
    }
    if(dp[startIndex][endIndex]!=null){
        return dp[startIndex][endIndex];
    }
    if(st.charAt(startIndex) == st.charAt(endIndex)&& endIndex-startIndex-1==dyn(st,startIndex+1,endIndex-1,dp)){
        dp[startIndex][endIndex] = 2+endIndex-startIndex-1;
        return dp[startIndex][endIndex];
    }else{
        dp[startIndex][endIndex] = Math.max(dyn(st,startIndex+1,endIndex,dp),dyn(st,startIndex,endIndex-1,dp));
    }
    return dp[startIndex][endIndex];
}