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.
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]; }}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.