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 * 10⁵
word consists only of lowercase English letters.

Solutions

Solution 1: Two Pointers

Thinking

Compression writes a count (at most \(9\)) plus the character for each run. Manual indices often mishandle splits at \(9\).

groupby already yields runs; each run is then cut into chunks of size at most \(9\).

For a run of length \(k\) append str(x)+c with \(x=\min(9,k)\) until \(k\) is exhausted.

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

Python3JavaC++GoTypeScriptJavaScript

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)

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

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

/**
 * @param {string} word
 * @return {string}
 */
var compressedString = function (word) {
    const ans = [];
    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('');
};

Solution 2: Two Pointers

Thinking

Method 1 uses a grouping helper. Two pointers can cut on a letter change or when the run reaches \(9\), without intermediate lists.

Keep the run start \(j\). When \(i\) hits the end, a new letter, or length \(9\), emit \(i-j\) and \(word[j]\) and set \(j=i\).

The scan ends at \(n\). Same linear bound, closer to the “at most nine” wording.

TypeScriptJavaScript

function compressedString(word: string): string {
    let res = '';

    for (let i = 1, j = 0; i <= word.length; i++) {
        if (word[i] !== word[j] || i - j === 9) {
            res += i - j + word[j];
            j = i;
        }
    }

    return res;
}

function compressedString(word) {
    let res = '';

    for (let i = 1, j = 0; i <= word.length; i++) {
        if (word[i] !== word[j] || i - j === 9) {
            res += i - j + word[j];
            j = i;
        }
    }

    return res;
}

Solution 3: RegExp

Thinking

Two pointers still encode the split by hand. The pattern (.)\1{0,8} matches one to nine equal characters.

A global search swallows each such run; the count is the match length.

Append len(m[0]) and the captured letter. The result matches the previous methods with less arithmetic.

TypeScriptJavaScript

function compressedString(word: string): string {
    const regex = /(.)\1{0,8}/g;
    let m: RegExpMatchArray | null = null;
    let res = '';

    while ((m = regex.exec(word))) {
        res += m[0].length + m[1];
    }

    return res;
}

function compressedString(word) {
    const regex = /(.)\1{0,8}/g;
    let m = null;
    let res = '';

    while ((m = regex.exec(word))) {
        res += m[0].length + m[1];
    }

    return res;
}

3163. String Compression III

Description

Solutions

Solution 1: Two Pointers

Solution 2: Two Pointers

Solution 3: RegExp

Comments