[LeetCode] 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.

压缩字符串 III。

给你一个字符串 word，请你使用以下算法进行压缩： - 从空字符串 comp 开始。当 word 不为空 时，执行以下操作： - 移除 word 的最长单字符前缀，该前缀由单一字符 c 重复多次组成，且该前缀长度 最多 为 9 。 - 将前缀的长度和字符 c 追加到 comp 。 返回字符串 comp 。

思路

这是一道模拟题。按照题意卡住条件即可，可直接参见代码。

复杂度

时间O(n)
空间O(n) - output 也是个字符串

代码

Java实现

class Solution {
    public String compressedString(String word) {
        StringBuilder sb = new StringBuilder();
        int n = word.length();
        int i = 0;
        int count = 0;
        while (i < n) {
            char cur = word.charAt(i);
            while (i < n && word.charAt(i) == cur && count < 9) {
                count++;
                i++;
            }
            sb.append(count);
            sb.append(cur);
            count = 0;
        }
        return sb.toString();
    }
}