Skip to content

2707. Extra Characters in a String

Description

You are given a 0-indexed 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.

 

Example 1:

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.

Example 2:

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.

 

Constraints:

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

Solutions

Solution 1: Hash Table + Dynamic Programming

Thinking

We want a partition of \(s\) that covers as many dictionary words as possible. Enumerating partitions is tolerable for \(n\le 50\), but identical prefixes would be recomputed.

The fewest extra characters among the first \(i\) letters depend only on shorter prefixes: treat \(s[i-1]\) as extra, or jump from some \(j\) whose slice \(s[j..i)\) is in the dictionary. A hash set answers membership in \(O(1)\), and we fill \(f[i]\) in increasing order.

We can use a hash table \(ss\) to record all words in the dictionary, which allows us to quickly determine whether a string is in the dictionary.

Next, we define \(f[i]\) to represent the minimum number of extra characters in the first \(i\) characters of string \(s\), initially \(f[0] = 0\).

When \(i \ge 1\), the \(i\)th character \(s[i - 1]\) can be an extra character, in which case \(f[i] = f[i - 1] + 1\). If there exists an index \(j \in [0, i - 1]\) such that \(s[j..i)\) is in the hash table \(ss\), then we can take \(s[j..i)\) as a word, in which case \(f[i] = f[j]\).

In summary, we can get the state transition equation:

\[ f[i] = \min \{ f[i - 1] + 1, \min_{j \in [0, i - 1]} f[j] \} \]

where \(i \ge 1\), and \(j \in [0, i - 1]\) and \(s[j..i)\) is in the hash table \(ss\).

The final answer is \(f[n]\).

The time complexity is \(O(n^3 + L)\), and the space complexity is \(O(n + L)\). Here, \(n\) is the length of string \(s\), and \(L\) is the sum of the lengths of all words in the dictionary.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def minExtraChar(self, s: str, dictionary: List[str]) -> int:
        ss = set(dictionary)
        n = len(s)
        f = [0] * (n + 1)
        for i in range(1, n + 1):
            f[i] = f[i - 1] + 1
            for j in range(i):
                if s[j:i] in ss and f[j] < f[i]:
                    f[i] = f[j]
        return f[n]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minExtraChar(String s, String[] dictionary) {
        Set<String> ss = new HashSet<>();
        for (String w : dictionary) {
            ss.add(w);
        }
        int n = s.length();
        int[] f = new int[n + 1];
        f[0] = 0;
        for (int i = 1; i <= n; ++i) {
            f[i] = f[i - 1] + 1;
            for (int j = 0; j < i; ++j) {
                if (ss.contains(s.substring(j, i))) {
                    f[i] = Math.min(f[i], f[j]);
                }
            }
        }
        return f[n];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int minExtraChar(string s, vector<string>& dictionary) {
        unordered_set<string> ss(dictionary.begin(), dictionary.end());
        int n = s.size();
        int f[n + 1];
        f[0] = 0;
        for (int i = 1; i <= n; ++i) {
            f[i] = f[i - 1] + 1;
            for (int j = 0; j < i; ++j) {
                if (ss.count(s.substr(j, i - j))) {
                    f[i] = min(f[i], f[j]);
                }
            }
        }
        return f[n];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func minExtraChar(s string, dictionary []string) int {
    ss := map[string]bool{}
    for _, w := range dictionary {
        ss[w] = true
    }
    n := len(s)
    f := make([]int, n+1)
    for i := 1; i <= n; i++ {
        f[i] = f[i-1] + 1
        for j := 0; j < i; j++ {
            if ss[s[j:i]] && f[j] < f[i] {
                f[i] = f[j]
            }
        }
    }
    return f[n]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function minExtraChar(s: string, dictionary: string[]): number {
    const ss = new Set(dictionary);
    const n = s.length;
    const f = new Array(n + 1).fill(0);
    for (let i = 1; i <= n; ++i) {
        f[i] = f[i - 1] + 1;
        for (let j = 0; j < i; ++j) {
            if (ss.has(s.substring(j, i))) {
                f[i] = Math.min(f[i], f[j]);
            }
        }
    }
    return f[n];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
use std::collections::HashSet;

impl Solution {
    pub fn min_extra_char(s: String, dictionary: Vec<String>) -> i32 {
        let ss: HashSet<String> = dictionary.into_iter().collect();
        let n = s.len();
        let mut f = vec![0; n + 1];
        for i in 1..=n {
            f[i] = f[i - 1] + 1;
            for j in 0..i {
                if ss.contains(&s[j..i]) {
                    f[i] = f[i].min(f[j]);
                }
            }
        }
        f[n]
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {string} s
 * @param {string[]} dictionary
 * @return {number}
 */
var minExtraChar = function (s, dictionary) {
    const ss = new Set(dictionary);
    const n = s.length;
    const f = Array(n + 1).fill(0);
    for (let i = 1; i <= n; ++i) {
        f[i] = f[i - 1] + 1;
        for (let j = 0; j < i; ++j) {
            if (ss.has(s.slice(j, i))) {
                f[i] = Math.min(f[i], f[j]);
            }
        }
    }
    return f[n];
};

Solution 2: Trie + Dynamic Programming

Thinking

Solution 1 enumerates every \(j\) for each \(i\) and builds slices, which cubes the time. Inserting reversed words into a trie lets us walk left from \(i-1\) and stop at the first miss, removing the slices and folding the lookup into the edges.

We can use a trie to optimize the time complexity of Solution 1.

Specifically, we first insert each word in the dictionary into the trie \(root\) in reverse order, then we define \(f[i]\) to represent the minimum number of extra characters in the first \(i\) characters of string \(s\), initially \(f[0] = 0\).

When \(i \ge 1\), the \(i\)th character \(s[i - 1]\) can be an extra character, in which case \(f[i] = f[i - 1] + 1\). We can also enumerate the index \(j\) in reverse order in the range \([0..i-1]\), and determine whether \(s[j..i)\) is in the trie \(root\). If it exists, then we can take \(s[j..i)\) as a word, in which case \(f[i] = f[j]\).

The time complexity is \(O(n^2 + L)\), and the space complexity is \(O(n + L \times |\Sigma|)\). Here, \(n\) is the length of string \(s\), and \(L\) is the sum of the lengths of all words in the dictionary. Additionally, \(|\Sigma|\) is the size of the character set. In this problem, the character set is lowercase English letters, so \(|\Sigma| = 26\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Node:
    __slots__ = ['children', 'is_end']

    def __init__(self):
        self.children: List[Node | None] = [None] * 26
        self.is_end = False


class Solution:
    def minExtraChar(self, s: str, dictionary: List[str]) -> int:
        root = Node()
        for w in dictionary:
            node = root
            for c in w[::-1]:
                i = ord(c) - ord('a')
                if node.children[i] is None:
                    node.children[i] = Node()
                node = node.children[i]
            node.is_end = True

        n = len(s)
        f = [0] * (n + 1)
        for i in range(1, n + 1):
            f[i] = f[i - 1] + 1
            node = root
            for j in range(i - 1, -1, -1):
                node = node.children[ord(s[j]) - ord('a')]
                if node is None:
                    break
                if node.is_end and f[j] < f[i]:
                    f[i] = f[j]
        return f[n]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Node {
    Node[] children = new Node[26];
    boolean isEnd;
}

class Solution {
    public int minExtraChar(String s, String[] dictionary) {
        Node root = new Node();
        for (String w : dictionary) {
            Node node = root;
            for (int k = w.length() - 1; k >= 0; --k) {
                int i = w.charAt(k) - 'a';
                if (node.children[i] == null) {
                    node.children[i] = new Node();
                }
                node = node.children[i];
            }
            node.isEnd = true;
        }
        int n = s.length();
        int[] f = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            f[i] = f[i - 1] + 1;
            Node node = root;
            for (int j = i - 1; j >= 0; --j) {
                node = node.children[s.charAt(j) - 'a'];
                if (node == null) {
                    break;
                }
                if (node.isEnd && f[j] < f[i]) {
                    f[i] = f[j];
                }
            }
        }
        return f[n];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Node {
public:
    Node* children[26];
    bool isEnd = false;
    Node() {
        fill(children, children + 26, nullptr);
    }
};

class Solution {
public:
    int minExtraChar(string s, vector<string>& dictionary) {
        Node* root = new Node();
        for (const string& w : dictionary) {
            Node* node = root;
            for (int k = w.length() - 1; k >= 0; --k) {
                int i = w[k] - 'a';
                if (node->children[i] == nullptr) {
                    node->children[i] = new Node();
                }
                node = node->children[i];
            }
            node->isEnd = true;
        }

        int n = s.size();
        int f[n + 1];
        f[0] = 0;
        for (int i = 1; i <= n; ++i) {
            f[i] = f[i - 1] + 1;
            Node* node = root;
            for (int j = i - 1; ~j; --j) {
                node = node->children[s[j] - 'a'];
                if (node == nullptr) {
                    break;
                }
                if (node->isEnd && f[j] < f[i]) {
                    f[i] = f[j];
                }
            }
        }
        return f[n];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
type Node struct {
    children [26]*Node
    isEnd    bool
}

func minExtraChar(s string, dictionary []string) int {
    root := &Node{}
    for _, w := range dictionary {
        node := root
        for k := len(w) - 1; k >= 0; k-- {
            i := int(w[k] - 'a')
            if node.children[i] == nil {
                node.children[i] = &Node{}
            }
            node = node.children[i]
        }
        node.isEnd = true
    }

    n := len(s)
    f := make([]int, n+1)
    for i := 1; i <= n; i++ {
        f[i] = f[i-1] + 1
        node := root
        for j := i - 1; j >= 0; j-- {
            node = node.children[int(s[j]-'a')]
            if node == nil {
                break
            }
            if node.isEnd && f[j] < f[i] {
                f[i] = f[j]
            }
        }
    }
    return f[n]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Node {
    children: (Node | null)[] = Array(26).fill(null);
    isEnd: boolean = false;
}

function minExtraChar(s: string, dictionary: string[]): number {
    const root = new Node();
    for (const w of dictionary) {
        let node = root;
        for (let k = w.length - 1; ~k; --k) {
            const i = w.charCodeAt(k) - 'a'.charCodeAt(0);
            if (node.children[i] === null) {
                node.children[i] = new Node();
            }
            node = node.children[i] as Node;
        }
        node.isEnd = true;
    }

    const n = s.length;
    const f: number[] = Array(n + 1).fill(0);
    for (let i = 1; i <= n; ++i) {
        f[i] = f[i - 1] + 1;
        let node = root;
        for (let j = i - 1; ~j; --j) {
            node = (node.children[s.charCodeAt(j) - 'a'.charCodeAt(0)] as Node) || null;
            if (node === null) {
                break;
            }
            if (node.isEnd && f[j] < f[i]) {
                f[i] = f[j];
            }
        }
    }

    return f[n];
}

Comments