Is Better Compression of String easy or hard?

Better Compression of String is generally rated Medium because the logic is straightforward but requires careful parsing of multi-digit numbers and correct aggregation of counts. Handling the input efficiently and producing sorted output without unnecessary work is the main challenge.

Better Compression of String Python/Java solution

Most implementations follow the same structure across languages: scan the string, parse the numeric count after each character, accumulate the value in a map or array, then output characters in sorted order with their totals. This logic translates directly to Python dictionaries, Java HashMap or arrays, and similar structures in C++, Go, or TypeScript.

How to solve Better Compression of String in O(n)?

Parse the string using two pointers: one reads the character and the other consumes all consecutive digits to form the count. Add the frequency to a 26-length counting array indexed by character. After processing the entire string, iterate alphabetically and append characters with their aggregated counts.

What is the best approach for Better Compression of String?

The optimal approach uses a counting array with two-pointer parsing. Traverse the string, extract each character and its multi-digit frequency, and accumulate counts in a fixed array of size 26. Finally iterate from 'a' to 'z' to build the sorted compressed result. This runs in O(n) time with O(1) extra space.

Is Better Compression of String asked at Google/Amazon/Meta?

String parsing and frequency aggregation problems like Better Compression of String frequently appear in interviews at companies such as Amazon, Google, and Meta. They test attention to detail, correct handling of multi-digit numbers, and efficient counting strategies.

What data structure is used in Better Compression of String?

The most common data structures are a hash table (for general character sets) or a fixed-size counting array for lowercase letters. Both store frequency totals while scanning the string. The array version is more efficient because it avoids sorting and extra memory overhead.

What is the time complexity of Better Compression of String?

The optimal solution runs in O(n) time where n is the length of the compressed string. Each character and digit is processed once during parsing. Using a fixed array for 26 letters keeps the space complexity O(1).

Description Hints 4 Solution Video 7:44

3167. Better Compression of String

Medium75.3% acceptance2 companiesPremium elsewhere, free here

You are given a string compressed representing a compressed version of a string. The format is a character followed by its frequency. For example, "a3b1a1c2" is a compressed version of the string "aaabacc".

We seek a better compression with the following conditions:

Each character should appear only once in the compressed version.
The characters should be in alphabetical order.

Return the better compression of compressed.

Note: In the better version of compression, the order of letters may change, which is acceptable.

Example 1:

Input: compressed = "a3c9b2c1"

Output: "a3b2c10"

Explanation:

Characters "a" and "b" appear only once in the input, but "c" appears twice, once with a size of 9 and once with a size of 1.

Hence, in the resulting string, it should have a size of 10.

Example 2:

Input: compressed = "c2b3a1"

Output: "a1b3c2"

Example 3:

Input: compressed = "a2b4c1"

Output: "a2b4c1"

Constraints:

1 <= compressed.length <= 6 * 10⁴
compressed consists only of lowercase English letters and digits.
compressed is a valid compression, i.e., each character is followed by its frequency.
Frequencies are in the range [1, 10⁴] and have no leading zeroes.

Asked at 2 companies

Riot Games Goldman Sachs

Topics

Hints open one at a time

Hint 1

This is an implementation problem.

Hint 2

Try to extract each character with its corresponding frequency.

Hint 3

Sum the frequencies for a single character.

Hint 4

Sort characters and append them to a string in alphabetical order.

7:44

Still stuck?Read the written solution, or watch a walkthrough.

Open solution