Extra Characters in a String
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
1We can break
s into "leet" from index 0 to 3 and "code" from index 5 to 8, leaving only the unused character at index 4.Example 2
Input
s = "sayhelloworld", dictionary = ["hello","world"]Output
3We can break
s into "hello" from index 3 to 7 and "world" from index 8 to 12, leaving the characters at indices 0, 1, and 2 as extra characters.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