Better Compression of String - Practice Coding Problems

Better Compression of String - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: compressed = "a3b1a1c2"

› Output: "a4b1c2"

💡 Note: Character 'a' appears with frequencies 3 and 1, total = 4. Character 'b' appears once with frequency 1. Character 'c' appears once with frequency 2. Result is sorted alphabetically: a4b1c2

Example 2 — Single Character

$ Input: compressed = "c1"

› Output: "c1"

💡 Note: Only one character 'c' with frequency 1, so result remains c1

Example 3 — Multiple Duplicates

$ Input: compressed = "a1b1b1a2"

› Output: "a3b2"

💡 Note: Character 'a' appears with frequencies 1 and 2, total = 3. Character 'b' appears with frequencies 1 and 1, total = 2. Sorted result: a3b2

Constraints

1 ≤ compressed.length ≤ 1000
compressed consists of lowercase English letters and digits
Each character in compressed is followed by its frequency
1 ≤ frequency ≤ 999

Visualization

Tap to expand

Understanding the Visualization

Input

Compressed string with duplicate characters: "a3b1a1c2"

Process

Parse pairs, accumulate frequencies, sort alphabetically

Output

Better compression with unique characters: "a4b1c2"

Key Takeaway

🎯 Key Insight: Use hash map to accumulate character frequencies, then sort keys alphabetically

Asked in

G Google 15 a Amazon 12 M Microsoft 10 🍎 Apple 8

The key insight is to parse character-frequency pairs and use a hash map to accumulate total frequencies for each character, then sort alphabetically. Best approach is Hash Map Frequency Counting with Time: O(n + k log k), Space: O(k) where k ≤ 26.

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map Frequency Counting	O(n + k log k)	O(k)	Use hash map to count character frequencies while parsing
Brute Force String Parsing	O(n²)	O(k)	Parse string character by character, count frequencies manually, then sort

Hash Map Frequency Counting — Algorithm Steps

Step 1: Parse string to extract character-frequency pairs
Step 2: Use hash map to accumulate frequencies for each character
Step 3: Sort characters alphabetically and construct result

Visualization

Tap to expand

Step-by-Step Walkthrough

Parse & Count

Extract pairs and update hash map frequencies

Sort Keys

Get characters in alphabetical order

Build Result

Construct final compressed string

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

int compare(const void* a, const void* b) {
    return (*(char*)a - *(char*)b);
}

char* solution(char* compressed) {
    int charCount[26] = {0};
    int present[26] = {0};
    
    // Parse character-frequency pairs
    int i = 0;
    int len = strlen(compressed);
    while (i < len) {
        char ch = compressed[i];
        i++;
        char freqStr[10] = {0};
        int freqIdx = 0;
        while (i < len && isdigit(compressed[i])) {
            freqStr[freqIdx++] = compressed[i];
            i++;
        }
        
        int freq = atoi(freqStr);
        charCount[ch - 'a'] += freq;
        present[ch - 'a'] = 1;
    }
    
    // Build result in alphabetical order
    char* result = malloc(1000);
    result[0] = '\0';
    
    for (int i = 0; i < 26; i++) {
        if (present[i]) {
            char temp[10];
            sprintf(temp, "%c%d", 'a' + i, charCount[i]);
            strcat(result, temp);
        }
    }
    
    return result;
}

int main() {
    char compressed[1000];
    fgets(compressed, sizeof(compressed), stdin);
    compressed[strcspn(compressed, "\n")] = 0;
    
    char* result = solution(compressed);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + k log k)

O(n) for parsing and counting, O(k log k) for sorting unique characters where k ≤ 26

⚡ Linearithmic

Space Complexity

O(k)

Hash map stores at most 26 unique characters

✓ Linear Space

25.6K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map Frequency Counting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler