README_EN.md

comments	difficulty	edit_url	tags
true	Medium	https://github.com/doocs/leetcode/edit/main/solution/3100-3199/3167.Better%20Compression%20of%20String/README_EN.md	Hash Table String Counting Sorting

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

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$.

Python3

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()))

Java

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();
    }
}

C++

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();
    }
};

Go

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()
}

TypeScript

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('');
}