647. Palindromic Substrings

Solution explanation

Q: Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

Example 1:

Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Approach:

Using dynamic programming approach we will form a matrix that consists of indices of two pointers in the given list and the values of say M[0][1] starting at index 0 and ending at index 1 is True is this substring is a palindrome else False

s = "abca"
n = len(s)
dp = [[0] * n for _ in range(n)]

then we loop through this matrix checking two rules:

• if the starting and ending values are equal and
• if the difference between the two pointers is less than 2, so we can ignore whatever element in the middle and consider the pattern as palindrome as for example “aba” so this is a palindrome even if we changed b to any value
• check if the in between pattern is a palindrome as well, i.e. have a true flag in the matrix like for example “abbba” is we are checking from index 0 to 4, if we checked we should have M[0] == M[4] both are equal to “a” the other rule is 4–0< 3 which is False the last rule if the inbetween pattern is a palindrome which is should be True,i.e M[i-1][j+1] = True,M[1][3]

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])
    res += dp[i][j]
res