Quick Overview

This question evaluates parsing of compact count-value encodings, reasoning about ambiguous encodings, and combinatorial enumeration of all valid decodings.

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.

Overview: 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

  1. 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.
  2. Disallow counts that start with '0'.
  3. Memoize by index to avoid recomputing decodings for the same suffix.
  4. Combine the current (count,value) expansion with all decodings of the remaining suffix.
  5. Sort the final results lexicographically for deterministic output.

Loading coding console...

Show the approach

Approach

We parse the string with DFS where each state is the current index i in s. At index i, try every possible count length (1..n-i-1) so that at least one digit remains for the value. Disallow counts with leading zeros. For each (count,value) choice, recursively decode the remainder starting at the next index and prepend count copies of value to each returned expansion. We memoize dfs(i) to avoid recomputing for the same suffix. Finally, we deduplicate and sort the list of expanded arrays lexicographically for deterministic output.

Time complexity:
O(U + R), where U is the number of DFS states explored (at most O(n^2)) and R is the total number of integers produced across all returned arrays; generating the expansions dominates.
Space complexity:
O(M + R), where M is memoization overhead (number of dfs states) and R is the total size of all returned arrays.