HackerRank Coding Interview 10.Palindrome Substrings — Part 2— Solution

Following is the solution of the problem described in the first part of this questionaire.

Optimal Solution:

​

First, we will find the substrings which are palindromes, and store the answer in the isPalindrome[n][n] 2D array.

If substring from (i, j) is a palindrome, then isPalindrome[i][j] will be true and vice versa.

Then let’s make an array dp[n] such that:

dp[i] represents the answer of the substring from (0, i) .

Now,

• dp[i] = dp[i-1] initially
• dp[i] = dp[j] + 1 (wherever substring(j+1, i) is a palindrome)

The final answer will be dp[n-1].

​

def getMaxSubstrings(s, k):
    # Write your code here
    n = len(s)
    is_palindrome = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            if i == j:
                is_palindrome[i][j] = 1
            if j == i + 1 and s[i] == s[j]:
                is_palindrome[i][j] = 1
            if j - i >= 2 and is_palindrome[i + 1][j - 1] == 1 and s[i] == s[j]:
                is_palindrome[i][j] = 1
    
    dp = [0] * (n + 1)…