3163. String Compression III
Description
Given a string word
, compress it using the following algorithm:
- Begin with an empty string
comp
. Whileword
is not empty, use the following operation:- Remove a maximum length prefix of
word
made of a single characterc
repeating at most 9 times. - Append the length of the prefix followed by
c
tocomp
.
- Remove a maximum length prefix of
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"
tocomp
. - For prefix
"aaaaa"
, append"5"
followed by"a"
tocomp
. - For prefix
"bb"
, append"2"
followed by"b"
tocomp
.
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
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
Solution 2: Two Pointers
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
Solution 3: RegExp
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|