Daily Challenge 09/23/2024: Extra Characters in String

Dynamic programming

See the leetcode problem statement here.

I am doing this one the day after. I cannot lie - I was stumped when I saw this question yesterday and so I read the editorial today. This post will serve as my notes.

Analysis

The algorithm is roughly:

1. Start from the beginning of the string. Assume that the first character is bad and recursively check for substrings in the dictionary as follows:

   • When the trivial substring is reached, there is nothing to look through, so there are no extra characters, otherwise go do 1.
   • Then for each such substring, iterate through the substring’s substrings in increasing order - when a word is found, do this for the remaining part of the string and keep the number of extra characters from this start point as the number of extra characters if it beats that found by 1.

Solution

My implementation is very much inspired by the editorial. So it is no surprise that it did reasonably well with \(76\%\) quantile in runtime and \(58\%\) in memory.

class Solution:
    def minExtraChar(self, s: str, dictionary: list[str]) -> int:

        n = len(s)
        dictionary_set = set(dictionary)

        def dp(start: int, memo: dict[int, int]):
            """This function should inspect the substring from ``n`` to its
            end."""

            # NOTE: If the end of the string is reached, there are no remaining
            #       characters.
            if start in memo:
                return memo[start]
            elif start == n:
                return 0

            # NOTE: Assume that start is bad. Count up the remaining
            #       characters and add one for the assumption that the start is
            #       bad.
            out = dp(start + 1, memo) + 1

            for end in range(start, n):
                if s[start : end + 1] in dictionary_set:
                    out_new = dp(end + 1, memo)

                    if out_new < out:
                        out = out_new

            memo[start] = out
            return out

        memo: dict[int, int] = dict()
        return dp(0, memo)