Valid Palindrome III

See all coding puzzles and patterns here.

Leetcode 1216 (Premium)
Difficulty: Hard
Patterns:
- Depth-First Search
- Two Pointer Technique

Problem Definition

Given a string $s$ and an integer $k$, determine if $s$ can be turned into a palindrome by removing at most $k$ characters from $s$. All spaces and punctuation characters should be ignored.

Such a string $s$ is said to be a K-Palindrome.

Examples

Some test cases to verify our solution.

assert k_pal("teammate", 2) # tammat
assert not k_pal("teammate", 1)
assert k_pal("racecars", 1)
assert not k_pal("his racecars", 1)
assert k_pal("his racecars", 2)

Recursive Solution

We use two pointers while comparing characters. Whenever the characters don't match, we will create 2 possibilities:

Skip the left character and decrement $k$.
Skip the right character and decrement $k$.

def helper(s: str, k: int, l: int, r: int) -> bool:
    while 1:
        if l > r:
            return True
        if s[l] == s[r]:
            l += 1
            r -= 1
        elif not s[l].isalnum():
            l += 1
        elif not s[r].isalnum():
            r -= 1
        elif k == 0:
            return False
        else:
            return helper(s, k - 1, l + 1, r) or helper(s, k - 1, l, r - 1)

def k_pal(s: str, k: int) -> bool:
    return helper(s, k, l=0, r=len(s) - 1)

Recursive Solution Complexity

Let $n =$ len(s).

Runtime complexity should be $O(n \cdot 2^k)$ since in the worst case, $k = n - 1$ and each character is unique, which will create $2^k$ branches, and each branch will traverse up to $n$ characters.

Auxiliary space complexity should be $O(k)$ since we might be storing up to $2 \cdot k$ items on the stack at any time, since this is a DFS traversal.

Iterative Solution

The principle is the same as the recursive solution, but we will use a custom stack instead of relying on the program's frame stack to compute our branches. We are essentially doing a depth-first search through the decision tree to find a node that results in a palindrome without exhausting $k$.

def k_pal_2(s: str, k: int) -> bool:
    # items of form (left pointer, right pointer, k remainder)
    stack = [(0, len(s) - 1, k)]
    while stack:
        l, r, k = stack.pop()
        while 1:
            if l > r:
                return True
            if s[l] == s[r]:
                l += 1
                r -= 1
            elif not s[l].isalnum():
                l += 1
            elif not s[r].isalnum():
                r -= 1
            elif k == 0:
                break
            else:
                stack.append((l + 1, r, k - 1))
                stack.append((l, r - 1, k - 1))
                break
    return False

Iterative Solution Complexity

Let $n = $ len(s).