3163. String Compression III

Problem Link

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:

  <ul>
  	<li>Remove a maximum length prefix of <code>word</code> made of a <em>single character</em> <code>c</code> repeating <strong>at most</strong> 9 times.</li>
  	<li>Append the length of the prefix followed by <code>c</code> to <code>comp</code>.</li>
  </ul>
  </li>
  

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.

Solution

---

Python3

class Solution:
    def compressedString(self, word: str) -> str:
        N = len(word)
        res = []
        curr = word[0]
        count = 1
 
        for i in range(1, N):
            if word[i] == curr:
                count += 1
            else:
                res.append(str(count) + curr)
                count = 1
                curr = word[i]
            
            if count == 10:
                res.append("9" + curr)
                count = 1
 
        res.append(str(count) + curr)
 
        return "".join(res)