Skip to main content
Talentd

Better Compression of String - Solution & Explanation

MediumPremiumFree on FleetCodeHash TableStringSortingCounting7 min readAsked at: Goldman Sachs, Riot Games
Practice this problem

Problem Statement

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:

  1. Each character should appear only once in the compressed version.
  2. 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 * 104
  • 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, 104] and have no leading zeroes.

Approach Overview

Problem Overview: You receive a compressed string such as a12b3a2, where each character is followed by a positive integer representing its frequency. Characters may appear multiple times and are not guaranteed to be in sorted order. The task is to combine the counts for identical characters and return a new compressed string with characters sorted alphabetically.

Approach 1: Hash Table + Parsing + Sorting (O(n + k log k) time, O(k) space)

Scan the string and extract each character with its numeric frequency. Use two pointers: one pointer reads the character and the second pointer advances through consecutive digits to build the full number. Store the accumulated frequency in a hash table where the key is the character and the value is the total count. After processing the entire string, sort the unique characters alphabetically and rebuild the compressed string using the aggregated counts. This approach is simple and flexible when the alphabet size is not fixed.

Approach 2: Counting Array + Two Pointers (O(n) time, O(1) space)

Since the problem deals with lowercase English letters, you can replace the hash table with a fixed array of size 26. Traverse the string using the same two‑pointer parsing strategy: read a character, then iterate through digits to construct its frequency. Convert the character to an index (c - 'a') and accumulate the count in the array. After parsing the entire string, iterate from a to z and append each character with its final count if the value is non‑zero. Because the alphabet size is constant, the result is naturally sorted and avoids an explicit sorting step.

The key implementation detail is parsing multi‑digit counts correctly. When you encounter a digit, repeatedly multiply the current number by 10 and add the next digit until a non‑digit character appears. This technique is common in string parsing problems and ensures counts like a123 are interpreted properly.

Recommended for interviews: The counting array approach is usually preferred. It runs in linear time O(n) with constant space and avoids sorting entirely. Starting with the hash table solution still demonstrates solid problem decomposition and understanding of frequency aggregation, but moving to the fixed-size counting structure shows awareness of constraints and optimization.

Solution

We can use a hash table to count the frequency of each character, and then use two pointers to traverse the compressed string, adding the frequency of each character to the hash table. Finally, we concatenate the characters and frequencies into a string in alphabetical order.

The time complexity is O(n + |\Sigma| log |\Sigma|), and the space complexity is O(|\Sigma|). Where n is the length of the string compressed, and |\Sigma| is the size of the character set. Here, the character set is lowercase letters, so |\Sigma| = 26.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Hash Table + Parsing + SortingO(n + k log k)O(k)General case when character set is not limited or when using a flexible frequency map
Counting Array + Two PointersO(n)O(1)Best when characters are limited (e.g., lowercase a–z) and sorted output is required

Video Solution

3167. Better Compression of String (Leetcode Medium) • Programming Live with Larry • 581 views views

Frequently Asked Questions

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).

Ready to solve this problem?

Practice Better Compression of String with our built-in code editor and test cases.

Practice on FleetCode
Previous

String Compression