2707. Extra Characters in a String - Explanation

Description

You are given a string s and a dictionary of words dictionary. You have to break s into one or more non-overlapping substrings such that each substring is present in dictionary. There may be some extra characters in s which are not present in any of the substrings.

Return the minimum number of extra characters left over if you break up s optimally.

Note that the same word in the dictionary may be reused multiple times.

Example 1:

Input: s = "neetcodes", dictionary = ["neet","code","neetcode"]

Output: 1

Explanation: The optimal way is to break s into two substrings: "neet" from index 0 to 3 and "code" from index 4 to 7. There is one character which is at index 8.

Example 2:

Input: s = "neetcodde", dictionary = ["neet","code","neetcode"]

Output: 5

Explanation: The optimal way is to break s into one substring: "neet" from index 0 to 3. The characters at indices from 4 to 8 are extra.

Constraints:

1 <= s.length <= 50
1 <= dictionary.length <= 50
1 <= dictionary[i].length <= 50
s and dictionary[i] consist of only lowercase English letters
dictionary contains distinct words

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Recursion

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

        def dfs(i):
            if i == len(s):
                return 0

            res = 1 + dfs(i + 1)
            for j in range(i, len(s)):
                if s[i:j + 1] in words:
                    res = min(res, dfs(j + 1))

            return res

        return dfs(0)

Time & Space Complexity

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

Where $n$ is the length of the string $s$ , $m$ is the number of words in the dictionary, and $k$ is the average length of a word in the dictionary.

2. Dynamic Programming (Top-Down) Using Hash Set

class Solution:
    def minExtraChar(self, s: str, dictionary: List[str]) -> int:
        words = set(dictionary)
        dp = {len(s): 0}

        def dfs(i):
            if i in dp:
                return dp[i]
            res = 1 + dfs(i + 1)
            for j in range(i, len(s)):
                if s[i:j + 1] in words:
                    res = min(res, dfs(j + 1))
            dp[i] = res
            return res

        return dfs(0)

Time & Space Complexity

Time complexity: $O(n ^ 3 + m * k)$
Space complexity: $O(n + m * k)$

Where $n$ is the length of the string $s$ , $m$ is the number of words in the dictionary, and $k$ is the average length of a word in the dictionary.

3. Dynamic Programming (Bottom-Up) Using Hash Set

class Solution:
    def minExtraChar(self, s: str, dictionary: List[str]) -> int:
        words = set(dictionary)
        n = len(s)
        dp = [0] * (n + 1)

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

Time & Space Complexity

Time complexity: $O(n ^ 3 + m * k)$
Space complexity: $O(n + m * k)$

Where $n$ is the length of the string $s$ , $m$ is the number of words in the dictionary, and $k$ is the average length of a word in the dictionary.

4. Dynamic Programming (Top-Down)

class Solution:
    def minExtraChar(self, s: str, dictionary: List[str]) -> int:
        dp = {len(s) : 0}

        def dfs(i):
            if i in dp:
                return dp[i]

            res = 1 + dfs(i + 1)
            for word in dictionary:
                if i + len(word) > len(s):
                    continue

                flag = True
                for j in range(len(word)):
                    if s[i + j] != word[j]:
                        flag = False
                        break
                if flag:
                    res = min(res, dfs(i + len(word)))

            dp[i] = res
            return res

        return dfs(0)

Time & Space Complexity

Time complexity: $O(n * m * k)$
Space complexity: $O(n)$

Where $n$ is the length of the string $s$ , $m$ is the number of words in the dictionary, and $k$ is the average length of a word in the dictionary.

5. Dynamic Programming (Bottom-Up)

class Solution:
    def minExtraChar(self, s: str, dictionary: List[str]) -> int:
        n = len(s)
        dp = [0] * (n + 1)

        for i in range(n - 1, -1, -1):
            dp[i] = 1 + dp[i + 1]
            for word in dictionary:
                if i + len(word) <= n and s[i:i + len(word)] == word:
                    dp[i] = min(dp[i], dp[i + len(word)])

        return dp[0]

Time & Space Complexity

Time complexity: $O(n * m * k)$
Space complexity: $O(n)$

Where $n$ is the length of the string $s$ , $m$ is the number of words in the dictionary, and $k$ is the average length of a word in the dictionary.

6. Dynamic Programming (Top-Down) Using Trie

class TrieNode:
    def __init__(self):
        self.children = {}
        self.isWord = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word):
        curr = self.root
        for c in word:
            if c not in curr.children:
                curr.children[c] = TrieNode()
            curr = curr.children[c]
        curr.isWord = True

class Solution:
    def minExtraChar(self, s: str, dictionary: List[str]) -> int:
        trie = Trie()
        for w in dictionary:
            trie.addWord(w)

        dp = {len(s): 0}

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

            dp[i] = res
            return res

        return dfs(0)

Time & Space Complexity

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

Where $n$ is the length of the string $s$ , $m$ is the number of words in the dictionary, and $k$ is the average length of a word in the dictionary.

7. Dynamic Programming (Bottom-Up) Using Trie

class TrieNode:
    def __init__(self):
        self.children = {}
        self.isWord = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word):
        curr = self.root
        for c in word:
            if c not in curr.children:
                curr.children[c] = TrieNode()
            curr = curr.children[c]
        curr.isWord = True

class Solution:
    def minExtraChar(self, s: str, dictionary: List[str]) -> int:
        trie = Trie()
        for w in dictionary:
            trie.addWord(w)

        n = len(s)
        dp = [0] * (n + 1)

        for i in range(n - 1, -1, -1):
            dp[i] = 1 + dp[i + 1]
            curr = trie.root
            for j in range(i, n):
                if s[j] not in curr.children:
                    break
                curr = curr.children[s[j]]
                if curr.isWord:
                    dp[i] = min(dp[i], dp[j + 1])

        return dp[0]

Time & Space Complexity

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

Where $n$ is the length of the string $s$ , $m$ is the number of words in the dictionary, and $k$ is the average length of a word in the dictionary.