Extra Characters in a String
MedPrompt
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 <= 501 <= dictionary.length <= 501 <= dictionary[i].length <= 50dictionary[i]andsconsists of only lowercase English lettersdictionarycontains distinct words
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly translates the problem into a recursive structure. We explore all possible ways to partition the string. At each position, we decide whether to skip the character (counting it as extra) or to match it as part of a dictionary word. This exhaustive search explores every possibility to find the minimum number of extra characters.
Algorithm
- Define a recursive function
solve(startIndex)that calculates the minimum extra characters for the suffix ofsstarting fromstartIndex. - Base Case: If
startIndexreaches the end of the string (s.length()), it means we have processed the entire string, so we return 0. - Recursive Step: For any
startIndex, we have two main choices:- Treat the character
s[startIndex]as an extra character. The cost for this choice is1 + solve(startIndex + 1). - Try to form a word from the dictionary starting at
startIndex. We iterate through all possible end indicesjfromstartIndextos.length() - 1. If the substrings.substring(startIndex, j + 1)exists in the dictionary, this is a valid move. The cost for this choice issolve(j + 1), as the characters in the word are not extra.
- Treat the character
- The function returns the minimum cost among all possible choices.
Walkthrough
The core idea is to define a function, let's say solve(i), which computes the minimum extra characters for the suffix of the string s starting at index i. To compute solve(i), we consider two possibilities. First, we can treat the character s[i] as an extra character. In this case, the total number of extra characters will be 1 (for s[i]) plus the result of the subproblem for the rest of the string, which is solve(i+1). Second, we can try to match a word from the dictionary that starts at index i. We check every substring s[i...j] (for j from i to n-1) against the dictionary. If a match is found, we've successfully covered that part of the string with zero extra characters, and we recursively call solve(j+1) to handle the remainder of the string. The final result for solve(i) is the minimum value obtained from all these possibilities. The initial call would be solve(0).
Complexity
Time
O(2^n * n * k), where n is the length of `s` and k is the average length of a dictionary word. The complexity is exponential because at each character, the function can branch, leading to a number of calls that grows exponentially with `n`. The additional factors account for substring creation and dictionary lookups.
Space
O(n), where n is the length of the string `s`. This space is used by the recursion call stack.
Trade-offs
Pros
Simple to understand and implement as it directly models the problem's decision-making process.
Cons
Extremely inefficient due to the massive number of redundant computations for the same subproblems.
Will lead to a 'Time Limit Exceeded' (TLE) error on any reasonably sized input.
This approach improves upon the brute-force recursion by using dynamic programming to avoid recomputing results for the same subproblems. We use a bottom-up approach, building the solution for the entire string from the solutions for its suffixes. An array dp is used, where dp[i] stores the minimum extra characters needed for the substring s starting at index i.
Algorithm
- First, convert the
dictionaryarray into aHashSetfor efficient O(1) average time lookups. - Create a DP array,
dp, of sizen + 1, wherenis the length ofs. dp[i]will store the minimum number of extra characters for the suffixs[i...].- Initialize
dp[n] = 0, as the empty suffix has no extra characters. - Iterate backwards from
i = n - 1down to0. - For each
i, first assumes[i]is an extra character, so setdp[i] = 1 + dp[i+1]. - Then, iterate with a second pointer
jfromiton - 1. Form the substringsub = s.substring(i, j + 1). - If
subis present in the dictionaryHashSet, it means we can form a word. This gives us another possible value fordp[i], which isdp[j + 1]. We updatedp[i]to be the minimum of its current value anddp[j + 1]. - After the loops complete,
dp[0]will hold the minimum extra characters for the entire strings.
Walkthrough
We define dp[i] as the minimum number of extra characters in the suffix s[i..n-1]. Our goal is to find dp[0]. The base case is dp[n] = 0, representing an empty string suffix which has zero extra characters. We compute the dp values iteratively, starting from the end of the string and moving backwards to the beginning. For each index i, we have two choices:
- Skip
s[i]: Treats[i]as an extra character. The cost is1 + dp[i+1]. - Form a word: Check every substring
s[i..j]starting ati. Ifs[i..j]is in the dictionary, we have the option of taking this word, and the cost would bedp[j+1]. We setdp[i]to the minimum value found among all these choices. To make dictionary lookups fast, we pre-process thedictionaryinto aHashSet.
import java.util.Arrays;import java.util.HashSet;import java.util.Set; class Solution { public int minExtraChar(String s, String[] dictionary) { int n = s.length(); Set<String> dictSet = new HashSet<>(Arrays.asList(dictionary)); int[] dp = new int[n + 1]; for (int i = n - 1; i >= 0; i--) { // Option 1: Treat s[i] as an extra character dp[i] = 1 + dp[i + 1]; // Option 2: Try to form a word starting at i for (int j = i; j < n; j++) { String sub = s.substring(i, j + 1); if (dictSet.contains(sub)) { dp[i] = Math.min(dp[i], dp[j + 1]); } } } return dp[0]; }}Complexity
Time
O(n^3). We have two nested loops for `i` and `j`, which is `O(n^2)`. Inside the inner loop, `s.substring(i, j + 1)` takes `O(n)` time in Java, leading to a total complexity of `O(n^3)`.
Space
O(n + L), where `n` is the length of `s` and `L` is the total number of characters in the dictionary. `O(n)` is for the `dp` array and `O(L)` is for storing the dictionary in a `HashSet`.
Trade-offs
Pros
Significantly more efficient than brute-force recursion.
Guaranteed to find the optimal solution by systematically building it up.
Passes the given constraints.
Cons
The time complexity of O(n^3) might be too slow for larger constraints, although it passes for this problem's specific limits.
The repeated creation of substrings inside the loops can be inefficient.
This is the most optimal approach, which refines the dynamic programming solution. The bottleneck in the previous DP approach was the repeated scanning and substring creation to find matching dictionary words. We can optimize this by using a Trie (Prefix Tree). By pre-processing the dictionary into a Trie, we can efficiently find all dictionary words that are prefixes of s starting from any position i in a single pass.
Algorithm
- Trie Node: Define a
TrieNodeclass, which contains an array of children (e.g., of size 26 for lowercase English letters) and a boolean flagisEndOfWord. - Build Trie: Create a Trie data structure and insert every word from the
dictionaryinto it. - DP Array: Create a
dparray of sizen + 1, wheredp[i]stores the minimum extra characters for the suffixs[i...]. Initializedp[n] = 0. - DP Calculation: Iterate
ifromn - 1down to0.- Set the default value
dp[i] = 1 + dp[i+1](for skippings[i]) - Start a traversal of the Trie from its root. Iterate with a pointer
jfromiton - 1. - For each character
s[j], try to move to the corresponding child in the Trie. - If at any point a path does not exist, break the inner loop, as no more words can be formed.
- If the current
TrieNodehasisEndOfWordset totrue, it meanss[i...j]is a valid word. We then have a potential better value fordp[i], which isdp[j + 1]. Updatedp[i] = min(dp[i], dp[j + 1]).
- Set the default value
- Result: The final answer is
dp[0].
Walkthrough
We use the same DP state dp[i] as in the previous approach. However, we change how we find matching words. Instead of generating substrings and checking for their existence in a set, we build a Trie from the dictionary. When calculating dp[i], we start traversing the Trie from its root using characters from s starting at index i. As we traverse with a pointer j from i to n-1, if the current node in the Trie marks the end of a word, we know that s.substring(i, j+1) is a dictionary word. This allows us to consider the option of taking this word and transitioning to the state dp[j+1]. This avoids the O(n) substring creation cost at each step of the inner loop, reducing the complexity of the DP calculation.
class Solution { class TrieNode { TrieNode[] children = new TrieNode[26]; boolean isEndOfWord = false; } public int minExtraChar(String s, String[] dictionary) { int n = s.length(); TrieNode root = new TrieNode(); for (String word : dictionary) { TrieNode curr = root; for (char c : word.toCharArray()) { if (curr.children[c - 'a'] == null) { curr.children[c - 'a'] = new TrieNode(); } curr = curr.children[c - 'a']; } curr.isEndOfWord = true; } int[] dp = new int[n + 1]; for (int i = n - 1; i >= 0; i--) { dp[i] = 1 + dp[i + 1]; // Default: skip s[i] TrieNode curr = root; for (int j = i; j < n; j++) { char c = s.charAt(j); if (curr.children[c - 'a'] == null) { break; // No word in dict starts with s[i...j+1] } curr = curr.children[c - 'a']; if (curr.isEndOfWord) { // Found a word s[i...j] dp[i] = Math.min(dp[i], dp[j + 1]); } } } return dp[0]; }}Complexity
Time
O(n*k + L), where `L` is the total number of characters in the dictionary, `n` is the length of `s`, and `k` is the maximum length of a word in the dictionary. `O(L)` is for building the Trie. The DP calculation takes `O(n*k)` because the outer loop runs `n` times, and the inner `j` loop runs at most `k` times (the maximum depth of the Trie).
Space
O(n + L), where `n` is for the `dp` array and `L` is the total number of characters in the dictionary for storing the Trie.
Trade-offs
Pros
The most efficient time complexity among all approaches.
Scales well even if the length of the string
swere larger.
Cons
The implementation is more complex due to the need for a Trie data structure.
Solutions
Solution
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]; }}/** * @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 ]; };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]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]; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.