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

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

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

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

Comments