Coding Puzzle: Find Number of Palindromic Substrings in a String

• Difficulty: Medium
• Patterns:
  • Dynamic Programming

Problem Definition

Given a string, return the number of palindromic substrings in the string.

Examples

Some test cases to verify our solution.

assert count_pals("aba") == 4 # "a", "b", "a" & "aba"
assert count_pals("peep") == 6 # "p", "e", "e", "p", "ee" & "peep"

Solution

We take each index in the string and each pair of adjacent indexes as the possible middles of palindromes. From there, we grow the palindrome out as much as possible, incrementing the palindrome count along the way.

def idxs_are_valid(l_idx, r_idx, s_len):
    return l_idx >= 0 and r_idx < s_len

def iterate(l_idx, r_idx, count):
    return l_idx - 1, r_idx + 1, count + 1

def count_pals(s):
    count = 0
    s_len = len(s)
    for idx in range(len(s)):
        l_idx, r_idx, count = iterate(idx, idx, count)
        while idxs_are_valid(l_idx, r_idx, s_len) and s[l_idx] == s[r_idx]:
            l_idx, r_idx, count = iterate(l_idx, r_idx, count)
        if idx + 1 < s_len and s[idx] == s[idx+1]:
            l_idx, r_idx, count = iterate(idx, idx+1, count)
            while idxs_are_valid(l_idx, r_idx, s_len) and s[l_idx] == s[r_idx]:
                l_idx, r_idx, count = iterate(l_idx, r_idx, count)
    return count

Complexity

Let $n = $ len(s).

Runtime complexity should be $O(n^2)$ since, in the worst case, the string is a single repeated character, implying that every substring is a palindrome.

Auxiliary space complexity should be $O(1)$ since we have just some scalar variables and only 2 stack frames at most.

Dynamic Programming Solution

Coming soon...