Extra Characters in a String
Medium · Tries · Array · Hash Table · String · Dynamic Programming · Trie
Problem
You are given a string s and an array of distinct words dictionary. Cut s into non-overlapping pieces so that some pieces are words in dictionary; the characters not covered by any chosen word are extra characters. A word may be used any number of times.
Return the minimum number of extra characters left over when s is split as well as possible.
Examples
Input: s = "catxdogs", dictionary = ["cat","dog","dogs"] Output: 1
Use "cat" and "dogs"; only the x is left over.
Input: s = "moonlight", dictionary = ["moon","light","ligh"] Output: 0
"moon" + "light" covers the whole string.
Input: s = "abc", dictionary = ["d"] Output: 3
No word appears, so every character is extra.
Constraints
- 1 <= s.length <= 50
- 1 <= dictionary.length <= 50
- 1 <= dictionary[i].length <= 50
- s and dictionary[i] consist of lowercase English letters
- dictionary contains distinct words
Approaches
- Baseline: test every substring against a set — time O(n^3), space O(n + L)
Follow-up
The same DP answers related questions by changing what the two moves cost. The use cases forbid leftovers and count the fewest words that spell s (or report that none do), and charge each leftover letter by its place in the alphabet.
Related problems
Start free on Cariara · Coding problems · System design studio
