3163. String Compression III

Description

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.

Solutions

Solution 1: Two Pointers

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

Finally, return the result.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the length of the

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

• 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;
}
};

• class Solution:
def compressedString(self, word: str) -> str:
g = groupby(word)
ans = []
for c, v in g:
k = len(list(v))
while k:
x = min(9, k)
ans.append(str(x) + c)
k -= x
return "".join(ans)


• func compressedString(word string) string {
ans := []byte{}
n := len(word)
for i := 0; i < n; {
j := i + 1
for j < n && word[j] == word[i] {
j++
}
k := j - i
for k > 0 {
x := min(9, k)
ans = append(ans, byte('0'+x))
ans = append(ans, word[i])
k -= x
}
i = j
}
return string(ans)
}

• function compressedString(word: string): string {
const ans: string[] = [];
const n = word.length;
for (let i = 0; i < n; ) {
let j = i + 1;
while (j < n && word[j] === word[i]) {
++j;
}
let k = j - i;
while (k) {
const x = Math.min(k, 9);
ans.push(x + word[i]);
k -= x;
}
i = j;
}
return ans.join('');
}