3167. Better Compression of String π
Description
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.
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.
Solutions
Solution 1: Hash Table + Two Pointers
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$.
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|