3163 - String Compression III

Given a string word, compress it using the following algorithm:

• Begin with an empty string comp. While word is not empty, use the following operation:
  • Remove a maximum length prefix of word made of a single character c repeating at most 9 times.
  • Append the length of the prefix followed by c to comp.

Return the string comp.

 Example 1:

Input: word = "abcde"

Output: "1a1b1c1d1e"

Explanation:

Initially, comp = "". Apply the operation 5 times, choosing "a", "b", "c", "d", and "e" as the prefix in each operation.

For each prefix, append "1" followed by the character to comp.

Example 2:

Input: word = "aaaaaaaaaaaaaabb"

Output: "9a5a2b"

Explanation:

Initially, comp = "". Apply the operation 3 times, choosing "aaaaaaaaa", "aaaaa", and "bb" as the prefix in each operation.

• For prefix "aaaaaaaaa", append "9" followed by "a" to comp.
• For prefix "aaaaa", append "5" followed by "a" to comp.
• For prefix "bb", append "2" followed by "b" to comp.

 Constraints:

• 1 <= word.length <= 2 * 105
• word consists only of lowercase English letters.

Solution 1: Two Pointers

We can use two pointers to count the consecutive occurrences of each character. Suppose the current character c$𝑐$c appears consecutively kk$𝑘$ times, then we divide kk$𝑘$ into several x x$𝑥$, each xx$𝑥$ is at most 99$9$, then we concatenate xx$𝑥$ and cc$𝑐$, and append each xx$𝑥$ and cc$𝑐$ to the result.

Finally, return the result.

The time complexity is O(n)O(n)$𝑂(𝑛)$, and the space complexity is O(n)O(n)$𝑂(𝑛)$.

C++

• class Solution {
  public:
      string compressedString(string word) {
          string ans;
          int n = word.length();
          for (int i = 0; i < n;) {
              int j = i + 1;
              while (j < n && word[j] == word[i]) {
                  ++j;
              }
              int k = j - i;
              while (k > 0) {
                  int x = min(9, k);
                  ans.push_back('0' + x);
                  ans.push_back(word[i]);
                  k -= x;
              }
              i = j;
          }
          return ans;
      }
  };

JAVA

• class Solution {
      public String compressedString(String word) {
          StringBuilder ans = new StringBuilder();
          int n = word.length();
          for (int i = 0; i < n;) {
              int j = i + 1;
              while (j < n && word.charAt(j) == word.charAt(i)) {
                  ++j;
              }
              int k = j - i;
              while (k > 0) {
                  int x = Math.min(9, k);
                  ans.append(x).append(word.charAt(i));
                  k -= x;
              }
              i = j;
          }
          return ans.toString();
      }
  }

PYTHON

• class Solution:
      def compressedString(self, word: str) -> str:
          ans = ""
          n = len(word)
          i = 0
          while i < n:
              j = i + 1
              while j < n and word[j] == word[i]:
                  j += 1
              k = j - i
              while k > 0:
                  x = min(9, k)
                  ans += str(x) + word[i]
                  k -= x
              i = j
          return ans