Decode and Explain Ambiguity in Compression Strings
Company: Pinterest
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
##### Scenario
Compression library that encodes an array as count-value pairs where value is one digit but count may be many digits.
##### Question
Implement decode(s) that turns a string such as "1234" into the expanded list [2,4,4,4]. Explain why input "12114" is ambiguous and output all valid decodings.
##### Hints
DFS with memoisation over index; at each step parse 1–n digit count followed by one digit value.
Quick Answer: This question evaluates parsing of compact count-value encodings, reasoning about ambiguous encodings, and combinatorial enumeration of all valid decodings.
You are given a string s consisting only of digits. Interpret s as a concatenation of pairs, where each pair is a positive integer count (no leading zeros) immediately followed by a single-digit value (0–9). Because the count can be multiple digits, s may have multiple valid partitions into such pairs. For every valid partition, produce the expanded array by repeating each value exactly count times, preserving order. Return all expanded arrays, sorted lexicographically. If s cannot be fully partitioned into valid pairs, return an empty list.
For example, the string "12114" is ambiguous because it can be partitioned as (1,2)(11,4), (12,1)(1,4), or (1211,4), each yielding a different expanded array.
Constraints
- 1 <= len(s) <= 30
- s contains only digits '0'..'9'
- Each pair is: count (positive integer, no leading zeros) followed by value (single digit 0..9)
- Return all expanded arrays sorted lexicographically (standard list ordering)
- If no valid partition exists, return []
- In test data, the total number of integers across all returned arrays will not exceed 1e5
Examples
Input: 12
Expected Output:
Input: 20
Expected Output:
Hints
- Use DFS/backtracking over the index. At each index, try all possible count lengths (1..k) as long as at least one digit remains for the value.
- Disallow counts that start with '0'.
- Memoize by index to avoid recomputing decodings for the same suffix.
- Combine the current (count,value) expansion with all decodings of the remaining suffix.
- Sort the final results lexicographically for deterministic output.