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: 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:
1
2
Input: compressed ="c2b3a1"Output: "a1b3c2"
Example 3:
1
2
Input: compressed ="a2b4c1"Output: "a2b4c1"
Constraints:
1 <= compressed.length <= 6 * 10^4
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, 10^4] and have no leading zeroes.
We need to sum the counts for each character, even if they appear multiple times in the input, and then output the result in alphabetical order. Parsing the string and using a hash map makes this efficient.
classSolution {
public: string betterCompression(string s) {
unordered_map<char, int> cnt;
int n = s.size(), i =0;
while (i < n) {
char c = s[i++];
int num =0;
while (i < n && isdigit(s[i])) num = num *10+ (s[i++] -'0');
cnt[c] += num;
}
string ans;
for (char c ='a'; c <='z'; ++c) {
if (cnt.count(c)) ans += c + to_string(cnt[c]);
}
return ans;
}
};
classSolution {
public String betterCompression(String s) {
Map<Character, Integer> cnt =new HashMap<>();
int n = s.length(), i = 0;
while (i < n) {
char c = s.charAt(i++);
int num = 0;
while (i < n && Character.isDigit(s.charAt(i))) num = num * 10 + (s.charAt(i++) -'0');
cnt.put(c, cnt.getOrDefault(c, 0) + num);
}
StringBuilder ans =new StringBuilder();
for (char c ='a'; c <='z'; ++c) {
if (cnt.containsKey(c)) ans.append(c).append(cnt.get(c));
}
return ans.toString();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
classSolution {
funbetterCompression(s: String): String {
val cnt = mutableMapOf<Char, Int>()
var i = 0while (i < s.length) {
val c = s[i++]
var num = 0while (i < s.length && s[i].isDigit()) num = num * 10 + (s[i++] - '0')
cnt[c] = cnt.getOrDefault(c, 0) + num
}
return ('a'..'z').filter { cnt.containsKey(it) }.joinToString("") { "${it}${cnt[it]}" }
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
classSolution:
defbetterCompression(self, s: str) -> str:
from collections import defaultdict
cnt: dict[str, int] = defaultdict(int)
i, n =0, len(s)
while i < n:
c = s[i]
i +=1 num =0while i < n and s[i].isdigit():
num = num *10+ int(s[i])
i +=1 cnt[c] += num
return''.join(f'{c}{cnt[c]}'for c in sorted(cnt))
impl Solution {
pubfnbetter_compression(s: String) -> String {
use std::collections::HashMap;
letmut cnt = HashMap::new();
let s = s.as_bytes();
letmut i =0;
while i < s.len() {
let c = s[i] aschar;
i +=1;
letmut num =0;
while i < s.len() && s[i].is_ascii_digit() {
num = num *10+ (s[i] -b'0') asi32;
i +=1;
}
*cnt.entry(c).or_insert(0) += num;
}
letmut ans = String::new();
for c inb'a'..=b'z' {
let ch = c aschar;
iflet Some(&v) = cnt.get(&ch) {
ans.push(ch);
ans +=&v.to_string();
}
}
ans
}
}