Extra Characters in a String Python Solution

lcpy gen -n 2707   # by problem number
lcpy gen -s extra_characters_in_a_string   # by problem name

Input: s = "leetscode", dictionary = ["leet","code","leetcode"]
Output: 1
Explanation: We can break s in two substrings: "leet" from index 0 to 3 and "code" from index 5 to 8. There is only 1 unused character (at index 4), so we return 1.

Input: s = "sayhelloworld", dictionary = ["hello","world"]
Output: 3
Explanation: We can break s in two substrings: "hello" from index 3 to 7 and "world" from index 8 to 12. The characters at indices 0, 1, 2 are not used in any substring and thus are considered as extra characters. Hence, we return 3.

class Solution:
    # Time: O(n^2 * m)
    # Space: O(n)
    def min_extra_char(self, s: str, dictionary: list[str]) -> int:
        n = len(s)
        word_set = set(dictionary)
        dp = [0] * (n + 1)

        for i in range(1, n + 1):
            dp[i] = dp[i - 1] + 1
            for j in range(i):
                if s[j:i] in word_set:
                    dp[i] = min(dp[i], dp[j])

        return dp[n]