Extra Characters in a String
Problem
Given a 0-indexed string s and a dictionary of words, break s into one or more non-overlapping substrings so that each substring appears in the dictionary. Some characters may be left over as extra characters that belong to no substring. Return the minimum number of extra characters if you break up s optimally.
s = "leetscode", dictionary = ["leet","code","leetcode"]1def minExtraChar(s, dictionary):
n = len(s)
words = set(dictionary) # acts like a trie membership test
dp = [0] * (n + 1) # dp[i] = min extra in s[i:]
for i in range(n - 1, -1, -1):
dp[i] = dp[i + 1] + 1 # option A: s[i] is extra
for j in range(i + 1, n + 1):
if s[i:j] in words: # s[i:j] is a dictionary word
dp[i] = min(dp[i], dp[j])
return dp[0]function minExtraChar(s, dictionary) {
const n = s.length;
const words = new Set(dictionary); // trie membership test
const dp = new Array(n + 1).fill(0); // dp[i] = min extra in s[i:]
for (let i = n - 1; i >= 0; i--) {
dp[i] = dp[i + 1] + 1; // option A: s[i] is extra
for (let j = i + 1; j <= n; j++) {
if (words.has(s.slice(i, j))) // s[i..j) is a word
dp[i] = Math.min(dp[i], dp[j]);
}
}
return dp[0];
}int minExtraChar(String s, String[] dictionary) {
int n = s.length();
Set<String> words = new HashSet<>(Arrays.asList(dictionary));
int[] dp = new int[n + 1]; // dp[i] = min extra in s[i:]
for (int i = n - 1; i >= 0; i--) {
dp[i] = dp[i + 1] + 1; // option A: s[i] is extra
for (int j = i + 1; j <= n; j++) {
if (words.contains(s.substring(i, j)))
dp[i] = Math.min(dp[i], dp[j]);
}
}
return dp[0];
}int minExtraChar(string s, vector<string>& dictionary) {
int n = s.size();
unordered_set<string> words(dictionary.begin(), dictionary.end());
vector<int> dp(n + 1, 0); // dp[i] = min extra in s[i:]
for (int i = n - 1; i >= 0; i--) {
dp[i] = dp[i + 1] + 1; // option A: s[i] is extra
for (int j = i + 1; j <= n; j++) {
if (words.count(s.substr(i, j - i)))
dp[i] = min(dp[i], dp[j]);
}
}
return dp[0];
}Explanation
This is a classic suffix dynamic programming problem. Let dp[i] be the minimum number of extra characters needed to cover the suffix s[i:]. The answer we want is dp[0], and the empty suffix costs nothing, so dp[n] = 0.
We fill the table from right to left. At each index i there are two choices. Option A: leave s[i] as an extra character — that costs one plus whatever the rest of the suffix needs, i.e. dp[i+1] + 1. Option B: if some substring s[i..j) is a dictionary word, we can consume it for free and continue from j, paying only dp[j]. We take the minimum over all such valid j.
Why is the dictionary lookup a trie task? Instead of slicing every substring and probing a hash set, you can walk a trie built from the dictionary one character at a time starting at i. Each step descends one trie edge; whenever you land on a node marked as the end of a word, that prefix s[i..j) is a valid word and you relax dp[i] with dp[j]. This avoids rebuilding substrings and stops early the moment no trie edge matches.
For clarity the code panes show the hash-set membership variant, which is the same algorithm with s[i:j] in words standing in for the trie descent. Both are O(1)-ish per word boundary in practice.
Example: for s = "leetscode" the optimal split is "leet" + (extra 's') + "code", leaving exactly one extra character, so dp[0] = 1.