Welcome to Subscribe On Youtube

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

Solution 2: Two Pointers

This implementation follows the required operations directly. It traverses the relevant values and updates its state as each value is processed. After all required states have been considered, the maintained result is returned.

Solution 3: RegExp

This implementation follows the required operations directly. It traverses the relevant values and updates its state as each value is processed. After all required states have been considered, the maintained result is returned.

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


// Solution 2
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;
}



// Solution 3
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;
}


  • /**
 * @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
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
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;
}

All Problems

All Solutions