3163. String Compression III

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:

Example 2:

Constraints:

• 1 <= word.length <= 2 * 105
• word consists only of lowercase English letters.

Approach 01:

#include <string>
using namespace std;

class Solution {
public:
    string compressedString(const string& inputWord) {
        const int wordLength = inputWord.length();
        string compressedWord;

        for (int i = 0, j = 0; i < wordLength; i = j) {
            int count = 0;
            while (j < wordLength && inputWord[j] == inputWord[i] && count < 9) {
                ++j;
                ++count;
            }
            compressedWord += to_string(count) + inputWord[i];
        }

        return compressedWord;
    }
};

class Solution:
    def compressedString(self, inputWord: str) -> str:
        wordLength = len(inputWord)
        compressedWord = ''

        i = 0
        while i < wordLength:
            count = 0
            j = i
            while j < wordLength and inputWord[j] == inputWord[i] and count < 9:
                j += 1
                count += 1
            compressedWord += str(count) + inputWord[i]
            i = j

        return compressedWord

Time Complexity

• Main Loop:

  The function iterates through the input string inputWord using two pointers, i and j. Each character in inputWord is processed at most once, making the loop run in \( O(N) \), where \( N \) is the length of inputWord.

• Overall Time Complexity:

  The overall time complexity is \( O(N) \).

Space Complexity

• Compressed String:

  The compressedWord string holds the compressed output, which, in the worst case, could be nearly as long as the input if each character is unique or grouped in short sequences. This results in \( O(N) \) space complexity.

• Other Variables:

  Other variables such as count and j are constants and do not add significant space usage.

• Overall Space Complexity:

  The overall space complexity is \( O(N) \).