String Compression 3

Problem

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.

Examples

Example 1:

1
2
3
4
5

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:

1
2
3
4
5
6
7
8

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`.

Solution

Method 1 - Count the continuous chars

1. Initialisation:
   • Initialise an empty string comp to store the compressed result.
   • Initialise i to traverse the word.
2. Loop through the word:
   • While i is less than the length of word:
     • Determine the current character c which is word[i].
     • Count the length of the prefix of c repeating, but limit the count to a maximum of 9.
     • Append the count followed by c to the comp string.
     • Increment i by the count to move to the next segment of the string.
3. Return the compressed string comp.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def compressedString(self, word: str) -> str:
        comp: str = ""
        i: int = 0
        
        while i < len(word):
            ch: str = word[i]
            cnt: int = 0
            while i < len(word) and word[i] == ch and cnt < 9:
                i += 1
                cnt += 1
            
            comp += str(cnt) + ch

        return comp

Complexity

• ⏰ Time complexity: O(n), where n is the length of the word. We traverse the word once.
• 🧺 Space complexity: O(n). In the worst case scenario the comp string can be of length 2n since each character can result in a numeric value and the character itself being appended.