palindromes.py

'''
compute the minimum number of removals in order to make the string palindrome
'''

def palindromic_substring(word):
    
    dp = [[-1 for _ in range(len(word) + 1)] for _ in range(len(word)+1)]

    def count_nr_chars(word, i, j, count):
        if dp[i][j] != -1:
            return dp[i][j]
            
        if i >= j:
            return count
        
        if word[i] == word[j]:
            value = count_nr_chars(word, i + 1, j - 1, count)
        else:
            value = min(count_nr_chars(word, i + 1, j, count + 1),
            count_nr_chars(word, i, j - 1, count + 1),
            count_nr_chars(word, i + 1, j - 1, count + 2))
        
        dp[i][j] = value
        return dp[i][j]

    return count_nr_chars(word, 0, len(word) - 1, 0)

print(palindromic_substring('zmlbc'))