Coding

Better Compression of String

Asked at

Adobe

Amazon

Goldman Sachs

Salesforce

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given a compressed string compressed representing a shortened version of an original string. The format consists of a character followed by its frequency. For example, "d5e2d2a4" is a compressed form of "dddddeeddaaaa".

The task is to return a better compression of the given string with the following conditions:

Each character should appear only once in the final output.
Characters should be sorted alphabetically in the output string.

Return the optimized compressed version of the string.

Input: compressed = "d4a3c2a2c5" Output: "a5c7d4" Explanation: The letter "a" appears twice (a3 and a2), so its total count is 3 + 2 = 5. The letter "c" appears twice (c2 and c5), so its total count is 2 + 5 = 7. The letter "d" appears once (d4). Sorting in alphabetical order, the result is "a5c7d4".

Input: compressed = "b6c4a2" Output: "a2b6c4" Explanation: As all the characters appears once, the final result after sorting will be a2b6c4

Input: compressed = "e3d4c2b1e2"

1 <= compressed.length <= 5 × 104
compressed consists only of lowercase English letters and digits.
compressed is valid, meaning each character is always followed by its frequency.
Frequencies are in the range [1, 104] and do not have leading zeroes.

cpp

class Solution {
public:
    string betterCompression(string compressed) {
        
    }
};

java

class Solution {
    public String betterCompression(String compressed) {
     
    }
}

python

class Solution:
    def betterCompression(self, compressed: str) -> str:

javascript

class Solution {
    betterCompression(compressed) {

    }
}

csharp

public class Solution {
    public string BetterCompression(string compressed) {
        // Write your code here
    }
}

func betterCompression(compressed string) string {

}

Stuck? Show a way to structure it+

01Scan one character, then consume every following digit as its complete count.
02Add the parsed count to that character's aggregate frequency.
03Sort the distinct characters and concatenate each character with its total count.
04Validate multi-digit counts and empty or malformed input according to the contract.

Reference answer

Walk through the compressed string with an index. The current position is the character. Advance a second index across all following digits and build the count as count = count * 10 + digit; this is essential because frequencies may contain more than one digit. Add the count to a map entry for the character, then continue from the next character. After parsing, sort the map's distinct keys alphabetically and append each key followed by its aggregated count. For d5e2d2a4, the map becomes {d: 7, e: 2, a: 4}, so the result is a4d7e2. Parsing is O(n). Sorting u distinct characters costs O(u log u), and the map uses O(u) space. If the alphabet is fixed and small, an array can replace the map and make output ordering effectively constant-time.

Then expect these follow-ups

How would you validate malformed input such as a missing count?
Tests: robust parsing
How would the solution change for arbitrary Unicode symbols?
Tests: representation

Hiring now

Salesforce has 1,420 open roles right now

Also hiring: Adobe

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Business Development Representative Belgium Market (Dutch Speaking)
Ireland - Dublin
Service Cloud Account Executive
France - Paris
Summer Intern 2027 - Content Writer
India - Bangalore

Or practice this question first

Next question