Problem Description

You are given a string compressed that represents a compressed version of a string. The compression format consists of a character followed by its frequency count. For example, "a3b1a1c2" represents the string "aaabacc" (3 'a's, 1 'b', 1 'a', 2 'c's).

Your task is to create a better compression of this string that follows these rules:

1. Each character appears only once in the compressed version (combine all occurrences of the same character)
2. Characters are arranged in alphabetical order

For the example "a3b1a1c2":

• The original represents: "aaabacc"
• Count all occurrences: 'a' appears 4 times total (3+1), 'b' appears 1 time, 'c' appears 2 times
• Better compression in alphabetical order: "a4b1c2"

The solution uses a hash table to accumulate the total count for each character. It parses the compressed string using two pointers:

• One pointer i identifies the current character
• Another pointer j reads the multi-digit frequency number that follows
• The frequency is built digit by digit: x = x * 10 + int(compressed[j])
• After processing all characters, the results are sorted alphabetically and concatenated into the final compressed string

The time complexity is O(n + k log k) where n is the length of the input string and k is the number of unique characters. The space complexity is O(k) for storing the character counts.

Intuition

The key insight is recognizing that the current compression format allows the same character to appear multiple times at different positions. To create a better compression, we need to merge all occurrences of each character into a single entry.

Think of it like organizing items in a warehouse - instead of having "3 apples here, 2 apples there, 1 apple over there", we want to say "6 apples total". This requires us to:

1. Parse and accumulate: We need to read through the compressed string and add up the total count for each character. This naturally points us toward using a hash table or dictionary where the key is the character and the value is the cumulative count.

2. Handle multi-digit numbers: The frequency after each character might be more than a single digit (e.g., "a12" means 12 'a's). We need a way to read these numbers completely. This suggests using two pointers - one to mark where we are, and another to scan ahead and collect all consecutive digits.

3. Sort the result: Once we have the total counts, alphabetical ordering is straightforward - we can sort the characters and build our output string.

The parsing strategy becomes clear when we think about how we'd manually process the string:

• Start at a character
• Move forward to read all the digits that form its count
• Add this count to our running total for that character
• Jump to the next character and repeat

This two-pointer approach naturally handles the variable-length numbers while ensuring we correctly parse each character-frequency pair. The formula x = x * 10 + int(compressed[j]) is the standard way to build a number from individual digits, reading left to right.

Learn more about Sorting patterns.

Solution Approach

The solution uses a hash table with two pointers technique to parse and aggregate the character frequencies.

Step 1: Initialize Data Structures

• Create a Counter (hash table) to store the cumulative frequency of each character
• Set up two pointers: i for the current position and n for the string length

Step 2: Parse the Compressed String The main parsing loop continues while i < n:

1. Identify the character: The character at position i is the letter we're processing

2. Extract the frequency number:

   • Start j at i + 1 (position after the character)
   • Initialize x = 0 to build the frequency number
   • While compressed[j] is a digit:
     • Build the number using x = x * 10 + int(compressed[j])
     • Move j forward
   • This handles multi-digit numbers like "12" or "100"

3. Update the counter:

   • Add the extracted frequency x to the counter for compressed[i]
   • This accumulates counts if the same character appears multiple times

4. Move to next character-frequency pair:

   • Set i = j to jump to the next character

Step 3: Build the Result After parsing all character-frequency pairs:

• Use cnt.items() to get all (character, total_frequency) pairs
• Format each pair as f"{k}{v}" (character followed by its count)
• Sort these strings alphabetically (Python sorts strings lexicographically by default)
• Join all formatted pairs into the final compressed string

Example Walkthrough with "a3b1a1c2":

• Parse "a3": cnt['a'] = 3
• Parse "b1": cnt['b'] = 1
• Parse "a1": cnt['a'] = 3 + 1 = 4
• Parse "c2": cnt['c'] = 2
• Sort and format: ["a4", "b1", "c2"]
• Join: "a4b1c2"

The time complexity is O(n + k log k) where n is the input length (for parsing) and k is the number of unique characters (for sorting). The space complexity is O(k) for the counter.

Example Walkthrough

Let's walk through the solution with the input "b2a3b1c2a1":

Initial Setup:

• Create an empty counter/hash table: cnt = {}
• Set i = 0, n = 10 (length of input)

Parsing Loop:

Iteration 1: i = 0

• Character: 'b' at position 0
• Build frequency: j = 1, read digits → x = 2
• Update counter: cnt['b'] = 2
• Move pointer: i = 2

Iteration 2: i = 2

• Character: 'a' at position 2
• Build frequency: j = 3, read digits → x = 3
• Update counter: cnt['a'] = 3
• Move pointer: i = 4

Iteration 3: i = 4

• Character: 'b' at position 4
• Build frequency: j = 5, read digits → x = 1
• Update counter: cnt['b'] = 2 + 1 = 3
• Move pointer: i = 6

Iteration 4: i = 6

• Character: 'c' at position 6
• Build frequency: j = 7, read digits → x = 2
• Update counter: cnt['c'] = 2
• Move pointer: i = 8

Iteration 5: i = 8

• Character: 'a' at position 8
• Build frequency: j = 9, read digits → x = 1
• Update counter: cnt['a'] = 3 + 1 = 4
• Move pointer: i = 10 (end of string)

Building Result:

• Counter contains: {'b': 3, 'a': 4, 'c': 2}
• Format each entry: ["b3", "a4", "c2"]
• Sort alphabetically: ["a4", "b3", "c2"]
• Join together: "a4b3c2"

Final Output: "a4b3c2"

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + |Σ| log |Σ|)

The algorithm consists of two main phases:

1. Parsing phase: The while loop iterates through the entire string once. For each character-number pair, it extracts the character and builds the number by processing consecutive digits. This takes O(n) time where n is the length of the compressed string.

2. Sorting and output phase: The sorted() function sorts the character-count pairs. Since there are at most |Σ| unique characters (where |Σ| = 26 for lowercase letters), sorting takes O(|Σ| log |Σ|) time. The join() operation then concatenates the sorted results, which takes O(|Σ|) time for iteration plus the time to build the output string.

Therefore, the total time complexity is O(n + |Σ| log |Σ|).

Space Complexity: O(|Σ|)

The space usage includes:

1. The Counter object cnt stores at most |Σ| character-count pairs, using O(|Σ|) space.

2. The sorted list comprehension creates a temporary list of at most |Σ| strings, requiring O(|Σ|) space.

3. The final output string requires space proportional to the number of unique characters and their counts, which is also bounded by O(|Σ|).

Since the character set consists of lowercase letters, |Σ| = 26, making the space complexity O(|Σ|) or O(26) = O(1) in practical terms.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling Multi-Digit Numbers Correctly

A common mistake is assuming each frequency is a single digit and using compressed[i+1] directly, which fails for inputs like "a12b5".

Incorrect approach:

# This only reads one digit!
frequency = int(compressed[i + 1])
i += 2

Correct approach:

# Build the complete number digit by digit
j = i + 1
frequency = 0
while j < len(compressed) and compressed[j].isdigit():
    frequency = frequency * 10 + int(compressed[j])
    j += 1
i = j

2. Forgetting to Accumulate Counts for Duplicate Characters

Another pitfall is replacing the count instead of adding to it when the same character appears multiple times in the input.

Incorrect approach:

# This overwrites previous counts!
char_count[current_char] = frequency

Correct approach:

# Accumulate the counts
char_count[current_char] += frequency
# Or use Counter which handles this automatically

3. Incorrect String Concatenation in Result

When building the final result, forgetting to convert the frequency to string or not sorting alphabetically leads to wrong output.

Incorrect approaches:

# Missing alphabetical sort
result = "".join(f"{char}{count}" for char, count in char_count.items())

# Or trying to concatenate without string conversion
result = "".join(char + count for char, count in char_count.items())  # TypeError!

Correct approach:

# Sort and properly format as strings
result = "".join(sorted(f"{char}{count}" for char, count in char_count.items()))

4. Index Out of Bounds When Parsing

Not checking boundaries when reading digits can cause index errors, especially at the end of the string.

Incorrect approach:

while compressed[j].isdigit():  # Missing boundary check!
    frequency = frequency * 10 + int(compressed[j])
    j += 1

Correct approach:

while j < len(compressed) and compressed[j].isdigit():
    frequency = frequency * 10 + int(compressed[j])
    j += 1