CODEWITHSUNDEEP
stringalgorithmdynamic-programming
testing09
testing09

Reputation: 155

Number of Palindromic Substrings- error in dynamic programming

I'm trying to solve the number of palindromic substrings problem using DP.

The problem requires us to find the number of palindromic substrings in a string.

My current code is as follows:

def palindromic_substrings(s):
    result = 0

    dp = [[False] * len(s) for i in range(len(s))]

    for i in range(len(s)):
        for j in range(i, len(s)):
            dp[i][j] = j-i <= 1 or (s[i] == s[j] and dp[i+1][j-1])
            if dp[i][j]:
                result += 1
  
    return result

print(palindromic_substrings("aaa")) # returns 5- should be 6

My logic is a follows:

Let dp[i][j] represents whether the substring defined by s[i:j] is a palindromic substring. There are two cases to consider to determine dp[i][j].

The first is noticing that any substring of length less than 2 is always a palindrome i.e. j-i <= 1.

The second is that any substring that has length greater than 2 is a palindrome iff the first and last characters are the same and the inner substring, excluding the first and last characters is a palindrome i.e. s[i] == s[j] and dp[i+1][j-1].

If dp[i][j] is True i.e. it is palindromic, we increment the result.

My code is returning the wrong result and I'm unsure where the gap in my logic is.

Any help would be appreciated.

Upvotes: 2

Views: 229

Answers (1)

Daniel Hao
Daniel Hao

Reputation: 4980

This is inspired by @Stef great comments, so the working code will be like this: (credit to him, question for me... ;-)


def countSubstrings(self, s: str) -> int:
    n = len(s)
    dp = [[0] * n for _ in range(n)]
        
    ans = 0
    for i in range(n-1, -1, -1):
        for j in range(i, n):
            dp[i][j] = s[i] == s[j] and ((j-i+1) < 3 or dp[i+1][j-1])
            ans += dp[i][j]
    return ans

And this is non-DP version to compare:

 def countSubstrings(self, s: str) -> int:
     count = 0
     n = len(s)

     for i in range(2 * n - 1):

         left  =  i // 2
         right = (i+1) //  2
            
         while left >= 0 and right <n and s[left] == s[right]:
             count += 1
             left -= 1
             right += 1

     return count

Upvotes: 1

Related Questions