Skip to content

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:

  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.

 

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

Thinking

The string is runs of a letter plus a decimal count and must be merged in alphabetic order. Inserting into a sorted list of runs is awkward.

Only \(26\) letters appear, so counts can be accumulated and then emitted in key order. Two pointers parse each number.

Index \(i\) sits on a letter, \(j\) consumes digits into \(cnt\), and the answer joins sorted \(k+v\) pairs.

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
class Solution:
    def betterCompression(self, compressed: str) -> str:
        cnt = Counter()
        i, n = 0, len(compressed)
        while i < n:
            j = i + 1
            x = 0
            while j < n and compressed[j].isdigit():
                x = x * 10 + int(compressed[j])
                j += 1
            cnt[compressed[i]] += x
            i = j
        return "".join(sorted(f"{k}{v}" for k, v in cnt.items()))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public String betterCompression(String compressed) {
        Map<Character, Integer> cnt = new TreeMap<>();
        int i = 0;
        int n = compressed.length();
        while (i < n) {
            char c = compressed.charAt(i);
            int j = i + 1;
            int x = 0;
            while (j < n && Character.isDigit(compressed.charAt(j))) {
                x = x * 10 + (compressed.charAt(j) - '0');
                j++;
            }
            cnt.merge(c, x, Integer::sum);
            i = j;
        }
        StringBuilder ans = new StringBuilder();
        for (var e : cnt.entrySet()) {
            ans.append(e.getKey()).append(e.getValue());
        }
        return ans.toString();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    string betterCompression(string compressed) {
        map<char, int> cnt;
        int i = 0;
        int n = compressed.length();
        while (i < n) {
            char c = compressed[i];
            int j = i + 1;
            int x = 0;
            while (j < n && isdigit(compressed[j])) {
                x = x * 10 + (compressed[j] - '0');
                j++;
            }
            cnt[c] += x;
            i = j;
        }
        stringstream ans;
        for (const auto& entry : cnt) {
            ans << entry.first << entry.second;
        }
        return ans.str();
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func betterCompression(compressed string) string {
    cnt := map[byte]int{}
    n := len(compressed)
    for i := 0; i < n; {
        c := compressed[i]
        j := i + 1
        x := 0
        for j < n && compressed[j] >= '0' && compressed[j] <= '9' {
            x = x*10 + int(compressed[j]-'0')
            j++
        }
        cnt[c] += x
        i = j
    }
    ans := strings.Builder{}
    for c := byte('a'); c <= byte('z'); c++ {
        if cnt[c] > 0 {
            ans.WriteByte(c)
            ans.WriteString(strconv.Itoa(cnt[c]))
        }
    }
    return ans.String()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function betterCompression(compressed: string): string {
    const cnt = new Map<string, number>();
    const n = compressed.length;
    let i = 0;

    while (i < n) {
        const c = compressed[i];
        let j = i + 1;
        let x = 0;
        while (j < n && /\d/.test(compressed[j])) {
            x = x * 10 + +compressed[j];
            j++;
        }
        cnt.set(c, (cnt.get(c) || 0) + x);
        i = j;
    }
    const keys = Array.from(cnt.keys()).sort();
    const ans: string[] = [];
    for (const k of keys) {
        ans.push(`${k}${cnt.get(k)}`);
    }
    return ans.join('');
}

Comments