Leetcode 2707. Extra Characters in a String

Problem

Leetcode 2707 - Extra Characters in a String

Example:

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.

Approach

Using DFS and TrieNodes, we can solve the question. For each word in dictionary, we add in TrieNode and using DFS, we get min extra character.

Here is the Python code for the solution:

class TrieNode:
    def __init__(self):
        self.letterMap = {}
        self.endOfWord = False

class Solution:
    def minExtraChar(self, s: str, dictionary: List[str]) -> int:
        root = TrieNode()

        for word in dictionary:
            curr = root
            for ch in word:
                if ch not in curr.letterMap:
                    curr.letterMap[ch] = TrieNode()
                curr = curr.letterMap[ch]
            curr.endOfWord = True

        dp = {len(s): 0}

        def dfs(i):
            if i in dp:
                return dp[i]
            res = 1 + dfs(i + 1)
            curr = root
            for j in range(i, len(s)):
                if s[j] not in curr.letterMap:
                    break
                curr = curr.letterMap[s[j]]
                if curr.endOfWord:
                    res = min(res, dfs(j + 1))

            dp[i] = res
            return res

        return dfs(0)      
    

Time Complexity and Space Complexity

Time Complexity: $O(n^2 + m * k)$ where $m$ number of words in dictionary $n$ is length of string s $k$ is the average length of a word in dicitonary

Space Complexity: $O(n^2 + m * k)$