#3163 String Compression III - Solution

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 * 10⁵
word consists only of lowercase English letters.

In #3163 String Compression III, the goal is to compress a string by grouping consecutive identical characters and representing each group with its count followed by the character. A key constraint is that the count for a single group cannot exceed 9, so longer sequences must be split into multiple segments.

The most efficient strategy is a single-pass traversal. Iterate through the string while tracking the current character and its frequency. Whenever the character changes or the count reaches 9, append the current count and character to the result and reset the counter. This ensures that long runs are split properly while preserving order.

Using a StringBuilder (or similar mutable string structure) helps avoid repeated string concatenation costs. Since each character is processed once, the approach runs in linear time. The algorithm requires only a few extra variables besides the output structure, making it space efficient.

Approach	Time Complexity	Space Complexity
Single-pass string traversal with grouping	O(n)	O(n) for output

Solutions (12)

Iterative Counting Approach

This approach involves iterating through the string and counting consecutive characters. For each new character, append the count and character to the output string. If the count reaches 9, append and reset it.

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), as we store the result string separately.

C C++Java Python C#JavaScript

1#include <stdio.h>
2#include <string.h>
3
4void compressString(const char* word) {
5    int length = strlen(word);
6    char result[length * 2 + 1]; // Max length is twice the input + null terminator
7    int index = 0;
8    for (int i = 0; i < length;) {
9        char current = word[i];
10        int count = 0;
11        while (i < length && word[i] == current && count < 9) {
12            ++i;
13            ++count;
14        }
15        result[index++] = '0' + count;
16        result[index++] = current;
17    }
18    result[index] = '\0'; // Null-terminate the string
19    printf("%s\n", result);
20}
21
22int main() {
23    compressString("abcde");
24    compressString("aaaaaaaaaaaaaabb");
25    return 0;
26}

Explanation

This C solution uses an iterative approach where we count occurrences of each character up to a maximum of 9. We construct the result string manually.

Sliding Window Approach

This approach is similar to the iterative approach but conceptualizes the counting as a sliding window over the input string. You increment the window until it changes character or hits the maximum prefix length.

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), as it constructs the output string.

C C++Java Python C#JavaScript

1using System;

class StringCompressor {
    public static string CompressString(string word) {
        System.Text.StringBuilder result = new System.Text.StringBuilder();
        int start = 0;
        while (start < word.Length) {
            char current = word[start];
            int end = start;
            while (end < word.Length && word[end] == current && end - start < 9) {
                end++;
            }
            int count = end - start;
            result.Append(count).Append(current);
            start = end;
        }
        return result.ToString();
    }

    public static void Main(string[] args) {
        Console.WriteLine(CompressString("abcde"));
        Console.WriteLine(CompressString("aaaaaaaaaaaaaabb"));
    }
}