Skip to content

3167. Better Compression of String

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  string betterCompression(string compressed) {
    string ans;
    vector<int> count(26);

    for (int i = 0; i < compressed.length();) {
      const char c = compressed[i++];
      int freq = 0;
      while (i < compressed.length() && isdigit(compressed[i]))
        freq = freq * 10 + (compressed[i++] - '0');
      count[c - 'a'] += freq;
    }

    for (char c = 'a'; c <= 'z'; ++c)
      if (count[c - 'a'] > 0)
        ans += c + to_string(count[c - 'a']);

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
  public String betterCompression(String compressed) {
    StringBuilder sb = new StringBuilder();
    int[] count = new int[26];

    for (int i = 0; i < compressed.length();) {
      final char c = compressed.charAt(i++);
      int freq = 0;
      while (i < compressed.length() && Character.isDigit(compressed.charAt(i)))
        freq = freq * 10 + (compressed.charAt(i++) - '0');
      count[c - 'a'] += freq;
    }

    for (char c = 'a'; c <= 'z'; ++c)
      if (count[c - 'a'] > 0)
        sb.append(c).append(count[c - 'a']);

    return sb.toString();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def betterCompression(self, compressed: str) -> str:
    count = collections.Counter()
    i = 0

    while i < len(compressed):
      c = compressed[i]
      i += 1
      freq = 0
      while i < len(compressed) and compressed[i].isdigit():
        freq = freq * 10 + int(compressed[i])
        i += 1
      count[c] += freq

    return ''.join([c + str(count[c])
                    for c in sorted(count.keys())])