3163. String Compression III

3163. String Compression III

Difficulty: Medium

Topics: String

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.

Hint:

1. Each time, just cut the same character in prefix up to at max 9 times. It’s always better to cut a bigger prefix.

Solution:

We can use a greedy approach to compress the string by taking the longest possible prefix of repeating characters (up to 9 occurrences at a time) and then appending the length of the prefix along with the character to the result.

Here's the step-by-step solution:

1. 
   

   Initialize Variables:

   
   
   
   
   
   • 
     comp (the compressed string) starts as an empty string.
   
   
   • Use a pointer or index i to track the position in the word.
   
   
   
   


2. 
   

   Loop through word:

   
   
   
   
   
   • While there are characters left in word, find the longest prefix of repeating characters that does not exceed 9 characters.
   
   
   • Count how many times the current character repeats consecutively, up to a maximum of 9.
   
   
   
   


3. 
   

   Append to Compressed String:

   
   
   
   
   
   • Append the count followed by the character to comp.
   
   
   • Move the pointer i forward by the number of characters processed.
   
   
   
   


4. 
   

   Return Result:

   
   
   
   
   
   • After processing the entire string, return the compressed string comp.
   
   
   
   

Let's implement this solution in PHP: a star on GitHub or sharing the post on your favorite social networks 😍.