Better Compression of String
Adobe
Amazon
Goldman Sachs
SalesforceThe 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
}
}go
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
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
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question