142. Repeated Characters in Dictionary Words Due To Faulty Keyboard

Repeated Characters in Dictionary Words Due To Faulty Keyboard

A user has a faulty keyboard where some keys get stuck, causing characters to repeat more than intended.

You are given the final typed string and a dictionary of valid words.

Return all possible words the user intended to type.

A dictionary word is considered a valid intended word if the typed string could have been produced from that word by repeating one or more characters due to stuck keys.

More formally:

The sequence of distinct character groups must remain the same in both strings.
For each corresponding character group, the typed string must contain the same character.
The count of a character in the typed string must be greater than or equal to the count of that character in the intended word.

For example, the typed string "heeellooo" could come from "hello", because:

h appears 1 time in both
e appears 3 times in the typed string and 1 time in the intended word
l appears 2 times in both
o appears 3 times in the typed string and 1 time in the intended word

Method Signature

List<String> possibleIntendedWords(String typed, List<String> dictionary)

Parameters

typed is the final string produced by the faulty keyboard.
dictionary contains valid, non-blanks and unique candidate words.

Return

Return all words from dictionary that could be the original intended word.

Preserve the same order in which valid words appear in dictionary.

Notes

A character may be repeated more than intended, but characters cannot disappear, change order, or introduce a new character group.
If no dictionary word is valid, return an empty list.

Constraints

1 ≤ typed.length() ≤ 10^4
1 ≤ dictionary.size() ≤ 10^4
1 ≤ dictionary[i].length() ≤ 10^4
All strings contain only lowercase English letters.
The sum of lengths of all words in dictionary does not exceed 2 * 10^5.

Examples

Example 1

possibleIntendedWords(typed = "heeellooo", dictionary = List.of("hello", "helo", "hi", "heeello"))

Output: List.of("hello", "helo", "heeello")

Explanation:

"hello" is valid because each character group matches and the typed counts are large enough.
"helo" is valid because the character groups are h - e - l - o in both strings, and each typed group count is greater than or equal to the intended count.
"hi" is invalid because the character groups do not match.
"heeello" is valid because the group order matches and each typed group has at least the intended count.

Example 2

possibleIntendedWords(typed = "ssuuunn", dictionary = List.of("sun", "ssun", "sunn", "soon"))

Output: List.of("sun", "ssun", "sunn")

Explanation:

"sun" is valid.
"ssun" is valid because the typed s group has count 2.
"sunn" is valid because the typed n group has count 2.
"soon" is invalid because the character groups differ.

Example 3

possibleIntendedWords(typed = "aabbcc", dictionary = List.of("abc", "aabbcc", "abbc", "abcc", "ac"))

Output: List.of("abc", "aabbcc", "abbc", "abcc")

Explanation:

All returned words have the same character group order a - b - c.
"ac" is invalid because it is missing the b group.

Example 4

possibleIntendedWords(typed = "kkkk", dictionary = List.of("k", "kk", "kkkk", "kkkkk"))

Output: List.of("k", "kk", "kkkk")

Explanation:

The typed string can come from any intended word whose single k group has count at most 4.
"kkkkk" is invalid because the intended count is greater than the typed count.