How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Find Dictionary Matches for a Jammed String

Quick Overview

This question evaluates string-processing and pattern-matching skills, specifically run-length grouping of consecutive characters and efficient dictionary lookup, within the Coding & Algorithms domain.

Find Dictionary Matches for a Jammed String

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given: - a dictionary of lowercase words - an input string `jammed_string` A keyboard may be stuck, so when typing an original word, any character may be repeated extra times. A character can only expand into more copies of itself; characters are never deleted, reordered, or replaced by a different character. A dictionary word is considered a match if, after grouping consecutive equal characters, both the word and `jammed_string` have: 1. the same sequence of character groups, and 2. for every group, the count in `jammed_string` is greater than or equal to the count in the original word. Return all dictionary words that could have produced `jammed_string`. Examples: - `help` can produce `hellp` - `hello` can produce `hheellllo` - `banana` can produce `baanaaannnaaa` If multiple words match, return all of them. Follow-ups: 1. How would you preprocess the dictionary so that each query does not scan every word? 2. After filtering by compressed-character signature, how can you avoid recomputing character groups and counts for every candidate on every query? 3. If all words in the same bucket share the same signature, what is the minimal information that must be stored per word inside that bucket?

Quick Answer: This question evaluates string-processing and pattern-matching skills, specifically run-length grouping of consecutive characters and efficient dictionary lookup, within the Coding & Algorithms domain.

Part 1: Find All Dictionary Words That Could Produce a Jammed String

You are given a list of dictionary words and one jammed string. A word could have produced the jammed string if, after grouping consecutive equal characters, both strings have the same group-character sequence and every group count in the jammed string is greater than or equal to the corresponding count in the word. Return every matching dictionary word in the same order they appear in the dictionary.

Constraints

0 <= len(dictionary_words) <= 10^4
0 <= len(jammed_string) <= 10^5
The sum of lengths of all dictionary words is at most 2 * 10^5
All strings contain only lowercase English letters

Examples

Input: (['help', 'hello', 'shell', 'hellp'], 'hellp')

Expected Output: ['help', 'hellp']

Explanation: help can expand its single l into ll, and hellp already matches exactly.

Input: (['hello', 'halo', 'heeello'], 'hheeellllo')

Expected Output: ['hello', 'heeello']

Loading coding console...

Part 2: Answer Many Jammed Queries with Signature Bucketing

You must answer many jammed-string queries against the same dictionary. Preprocess the dictionary so that each query does not scan every word. Use the fact that words with different compressed character signatures can never match. For each query, return all matching dictionary words in original dictionary order.

Constraints

0 <= len(dictionary_words) <= 10^4
0 <= len(queries) <= 10^4
The total length of all dictionary words plus all queries is at most 3 * 10^5
All strings contain only lowercase English letters

Examples

Input: (['help', 'hello', 'hellp', 'banana', 'bananaa', 'heeello'], ['hellp', 'hheeellllo', 'baanaaannnaaa', 'xyz'])

Expected Output: [['help', 'hellp'], ['hello', 'heeello'], ['banana', 'bananaa'], []]

Explanation: Each query only needs to inspect words from its matching signature bucket.

Input: (['a', 'aa'], [])

Expected Output: []

Explanation: No queries means no answers.

Input: ([], ['a', 'aaa'])

Expected Output: [[], []]

Explanation: An empty dictionary produces no matches for any query.

Input: (['a', 'aa', 'ab'], ['aaa', 'abb'])

Expected Output: [['a', 'aa'], ['ab']]

Explanation: aaa matches the single-group bucket, while abb matches only ab.

Hints

Build a hash map from compressed signature to the words that have that signature.
For a query, only compare against the bucket with the same signature.

Part 3: Reuse Precomputed Group Counts for Fast Repeated Queries

You still need to answer many jammed-string queries against one dictionary, but now you must avoid recomputing character groups and counts for the same dictionary word on every query. Precompute each word once into its compressed signature and group-count vector. For each query, compare only against words in the same signature bucket and use the stored count vectors.

Constraints

0 <= len(dictionary_words) <= 10^4
0 <= len(queries) <= 10^4
The total length of all dictionary words plus all queries is at most 3 * 10^5
All strings contain only lowercase English letters

Examples

Input: (['ab', 'aab', 'abb', 'aaabbb', 'xyz'], ['aaabbb', 'ab', 'aabbb', 'xxyzzz'])

Expected Output: [['ab', 'aab', 'abb', 'aaabbb'], ['ab'], ['ab', 'aab', 'abb'], ['xyz']]

Explanation: After signature filtering, each candidate is checked using only its stored counts.

Input: (['hello', 'heeello'], ['halo'])

Expected Output: [[]]

Explanation: The query has a different signature, so no bucket matches.

Input: ([], ['a', 'aa'])

Expected Output: [[], []]

Explanation: No dictionary words means no matches.

Input: (['a'], [])

Expected Output: []

Explanation: No queries means no output rows.

Hints

Store each dictionary word as a pair of its original word and its group-count vector, keyed by signature.
Inside one signature bucket, matching becomes a simple component-wise comparison of integer arrays.

Part 4: Match a Same-Signature Bucket Using Only Group Counts

All words in one bucket already share the same compressed character signature, so the minimal per-word information you need to keep is just that word's list of group counts. You are given entries as pairs of a word and its count vector. For each query count vector, return all words whose counts are component-wise less than or equal to the query. Preserve the original entry order. If a query has a different number of groups, it cannot match any word in the bucket.

Constraints

0 <= len(entries) <= 10^4
0 <= len(queries) <= 10^4
All entries in the bucket are guaranteed to represent the same hidden signature
1 <= len(counts) <= 100 for every non-empty entry
All count values are positive integers

Examples

Input: ([('help', [1, 1, 1, 1]), ('hellp', [1, 1, 2, 1]), ('heeelp', [1, 3, 1, 1])], [[1, 1, 2, 1], [2, 3, 4, 1], [1, 1, 1]])

Expected Output: [['help', 'hellp'], ['help', 'hellp', 'heeelp'], []]

Explanation: The third query has the wrong number of groups, so it matches nothing.

Input: ([], [[1], [2]])

Expected Output: [[], []]

Explanation: An empty bucket yields no matches for any query.

Input: ([('a', [1]), ('aa', [2])], [[1], [3]])

Expected Output: [['a'], ['a', 'aa']]

Explanation: The second query can accommodate both stored count vectors.

Input: ([('aaa', [3]), ('aaaaa', [5])], [[4], [5]])

Expected Output: [['aaa'], ['aaa', 'aaaaa']]

Explanation: Counts are compared component-wise within a single-group bucket.

Hints

Because the signature is shared by the whole bucket, you never need to compare characters per word.
A word matches exactly when every stored count is less than or equal to the corresponding query count.