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:

  1. Each character should appear only once in the compressed version.
  2. 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.

Examples

Example 1:

1
2
3
4
5

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.

Solution

Method 1 – Hash Map and Parsing

Intuition

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.

Approach

  1. Initialize a hash map to store counts for each character.
  2. Parse the input string:
    • For each character, read the following digits as its count.
    • Add the count to the hash map for that character.
  3. Sort the characters alphabetically.
  4. Build the result string by concatenating each character and its total count.
  5. Return the result string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

func betterCompression(s string) string {
    cnt := map[byte]int{}
    n := len(s)
    for i := 0; i < n; {
        c := s[i]
        i++
        num := 0
        for i < n && s[i] >= '0' && s[i] <= '9' {
            num = num*10 + int(s[i]-'0')
            i++
        }
        cnt[c] += num
    }
    ans := ""
    for c := byte('a'); c <= 'z'; c++ {
        if v, ok := cnt[c]; ok {
            ans += string(c) + strconv.Itoa(v)
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    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

class Solution {
    fun betterCompression(s: String): String {
        val cnt = mutableMapOf<Char, Int>()
        var i = 0
        while (i < s.length) {
            val c = s[i++]
            var num = 0
            while (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

class Solution:
    def betterCompression(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 = 0
            while 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))
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

impl Solution {
    pub fn better_compression(s: String) -> String {
        use std::collections::HashMap;
        let mut cnt = HashMap::new();
        let s = s.as_bytes();
        let mut i = 0;
        while i < s.len() {
            let c = s[i] as char;
            i += 1;
            let mut num = 0;
            while i < s.len() && s[i].is_ascii_digit() {
                num = num * 10 + (s[i] - b'0') as i32;
                i += 1;
            }
            *cnt.entry(c).or_insert(0) += num;
        }
        let mut ans = String::new();
        for c in b'a'..=b'z' {
            let ch = c as char;
            if let Some(&v) = cnt.get(&ch) {
                ans.push(ch);
                ans += &v.to_string();
            }
        }
        ans
    }
}

Complexity

  • ⏰ Time complexity: O(n) — Each character and digit is processed once.
  • 🧺 Space complexity: O(1) — Only 26 possible characters.