3163. String Compression III - Solution & Code

Q: Is String Compression III easy or hard?

String Compression III is classified as a Medium problem on LeetCode. The logic is straightforward once you recognize it as a run-length encoding variant, but handling the "maximum count of 9 per group" constraint adds a small twist.

Q: String Compression III Python/Java solution

In Python or Java, iterate through the string while counting consecutive characters. When the count hits 9 or the character changes, append the count and character to a result builder (like a list in Python or StringBuilder in Java). This produces the compressed output in linear time.

Q: How to solve String Compression III in O(n)?

Traverse the string and maintain a counter for consecutive identical characters. When the count reaches 9 or the character changes, append the compressed segment (count followed by the character) and reset the counter. This single-pass strategy guarantees O(n) time complexity.

Q: What is the best approach for String Compression III?

The iterative counting approach is the most common solution. You scan the string once, count consecutive characters, and append "count + character" to the result whenever the count reaches 9 or the character changes. This achieves O(n) time complexity with constant auxiliary space.

Q: Is String Compression III asked at Google/Amazon/Meta?

String compression and run-length encoding variations appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary slightly, the core idea of grouping consecutive characters and limiting counts is a common string-processing pattern.

Q: What data structure is used in String Compression III?

The problem mainly uses basic string traversal and counters. No advanced data structures are required—just variables to track the current character and its frequency, plus a string builder or buffer for the compressed result.

Q: What is the time complexity of String Compression III?

The optimal solution runs in O(n) time because each character in the string is processed exactly once. Both the iterative counting and sliding window approaches maintain a single pass over the input. Space complexity is O(1) excluding the output string.

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

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.

Approach overview

Problem Overview: Given a string word, build a compressed version where each group of consecutive identical characters is replaced with count + character. Each count can be at most 9, so longer runs must be split into multiple groups (e.g., 12 'a' → 9a3a).

Approach 1: Iterative Counting Approach (O(n) time, O(1) extra space)

Traverse the string from left to right and count consecutive occurrences of the same character. Maintain a running counter for the current character and append count + char whenever the count reaches 9 or the character changes. Reset the counter and continue scanning. This works because the compression rule only depends on contiguous characters, so a single pass with simple counting is sufficient. The algorithm processes each character once, giving O(n) time complexity with O(1) auxiliary space (excluding the output string).

Approach 2: Sliding Window Approach (O(n) time, O(1) extra space)

Use two pointers to form a window over runs of identical characters. The left pointer marks the start of a group, while the right pointer expands while the same character continues and the group size stays under 9. When the window reaches size 9 or encounters a different character, append the compressed segment and move the left pointer forward. This is a natural application of the sliding window pattern on a string, where the window represents the current run of identical characters. Every character enters and exits the window once, so the runtime remains O(n) with constant extra space.

Recommended for interviews: The iterative counting approach is typically expected. It demonstrates that you can process a string efficiently with a single pass and handle edge cases like runs longer than 9. The sliding window version shows familiarity with two-pointer patterns and is equally optimal, but the counting approach is usually the most straightforward explanation during interviews.

Approach 1: 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.

Python

def compress_string(word):
    result = []
    i = 0
    while i < len(word):
        current = word[i]
        count = 0
        while i < len(word) and word[i] == current and count < 9:
            i += 1
            count += 1
        result.append(f'{count}{current}')
    return ''.join(result)

print(compress_string('abcde'))
print(compress_string('aaaaaaaaaaaaaabb'))

Java

public class StringCompressor {
    public static String compressString(String word) {
        StringBuilder result = new StringBuilder();
        int i = 0;
        while (i < word.length()) {
            char current = word.charAt(i);
            int count = 0;
            while (i < word.length() && word.charAt(i) == current && count < 9) {
                i++;
                count++;
            }
            result.append(count).append(current);
        }
        return result.toString();
    }

    public static void main(String[] args) {
        System.out.println(compressString("abcde"));
        System.out.println(compressString("aaaaaaaaaaaaaabb"));
    }
}

C++

#include <iostream>
#include <string>

std::string compressString(const std::string& word) {
    std::string result;
    int i = 0;
    while (i < word.length()) {
        char current = word[i];
        int count = 0;
        while (i < word.length() && word[i] == current && count < 9) {
            ++i;
            ++count;
        }
        result += std::to_string(count) + current;
    }
    return result;
}

int main() {
    std::cout << compressString("abcde") << std::endl;
    std::cout << compressString("aaaaaaaaaaaaaabb") << std::endl;
    return 0;
}

JavaScript

function compressString(word) {
    let result = '';
    let i = 0;
    while (i < word.length) {
        let current = word[i];
        let count = 0;
        while (i < word.length && word[i] === current && count < 9) {
            i++;
            count++;
        }
        result += count + current;
    }
    return result;
}

console.log(compressString('abcde'));
console.log(compressString('aaaaaaaaaaaaaabb'));

#include <stdio.h>
#include <string.h>

void compressString(const char* word) {
    int length = strlen(word);
    char result[length * 2 + 1]; // Max length is twice the input + null terminator
    int index = 0;
    for (int i = 0; i < length;) {
        char current = word[i];
        int count = 0;
        while (i < length && word[i] == current && count < 9) {
            ++i;
            ++count;
        }
        result[index++] = '0' + count;
        result[index++] = current;
    }
    result[index] = '\0'; // Null-terminate the string
    printf("%s\n", result);
}

int main() {
    compressString("abcde");
    compressString("aaaaaaaaaaaaaabb");
    return 0;
}

using System;

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

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

This Python solution uses a list to build the result string efficiently, iterating through the input with nested loops to count characters.

Complexity

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), due to storing the result in a list.

Try this approach in the editor

Approach 2: 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.

Python

def compress_string(word):
    result = []
    start = 0
    while start < len(word):
        current = word[start]
        end = start
        while end < len(word) and word[end] == current and end - start < 9:
            end += 1
        count = end - start
        result.append(f'{count}{current}')
        start = end
    return ''.join(result)

print(compress_string('abcde'))
print(compress_string('aaaaaaaaaaaaaabb'))

Java

public class StringCompressor {
    public static String compressString(String word) {
        StringBuilder result = new StringBuilder();
        int start = 0;
        while (start < word.length()) {
            char current = word.charAt(start);
            int end = start;
            while (end < word.length() && word.charAt(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) {
        System.out.println(compressString("abcde"));
        System.out.println(compressString("aaaaaaaaaaaaaabb"));
    }
}

C++

#include <iostream>
#include <string>

std::string compressString(const std::string& word) {
    std::string result;
    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 += std::to_string(count) + current;
        start = end;
    }
    return result;
}

int main() {
    std::cout << compressString("abcde") << std::endl;
    std::cout << compressString("aaaaaaaaaaaaaabb") << std::endl;
    return 0;
}

JavaScript

function compressString(word) {
    let result = '';
    let start = 0;
    while (start < word.length) {
        let current = word[start];
        let end = start;
        while (end < word.length && word[end] === current && end - start < 9) {
            end++;
        }
        let count = end - start;
        result += count + current;
        start = end;
    }
    return result;
}

console.log(compressString('abcde'));
console.log(compressString('aaaaaaaaaaaaaabb'));

#include <stdio.h>
#include <string.h>

void compressString(const char* word) {
    int length = strlen(word);
    char result[length * 2 + 1];
    int index = 0, start = 0;
    while (start < length) {
        char current = word[start];
        int end = start;
        while (end < length && word[end] == current && end - start < 9) {
            ++end;
        }
        int count = end - start;
        result[index++] = '0' + count;
        result[index++] = current;
        start = end;
    }
    result[index] = '\0';
    printf("%s\n", result);
}

int main() {
    compressString("abcde");
    compressString("aaaaaaaaaaaaaabb");
    return 0;
}

using 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"));
    }
}

This Python solution uses a two-pointer technique to count and store sequences of repeated characters in the word string, appending results to a list and joining them at the end.

Complexity

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), due to storing the result in pieces before joining them.

Try this approach in the editor

Approach 3: Two Pointers

We can use two pointers to count the consecutive occurrences of each character. Suppose the current character c appears consecutively k times, then we divide k into several x, each x is at most 9, then we concatenate x and c, and append each x and c to the result.

Finally, return the result.

The time complexity is O(n), and the space complexity is O(n). Where n is the length of the

TypeScript

function compressedString(word: string): string {
    const ans: string[] = [];
    const n = word.length;
    for (let i = 0; i < n; ) {
        let j = i + 1;
        while (j < n && word[j] === word[i]) {
            ++j;
        }
        let k = j - i;
        while (k) {
            const x = Math.min(k, 9);
            ans.push(x + word[i]);
            k -= x;
        }
        i = j;
    }
    return ans.join('');
}

func compressedString(word string) string {
	ans := []byte{}
	n := len(word)
	for i := 0; i < n; {
		j := i + 1
		for j < n && word[j] == word[i] {
			j++
		}
		k := j - i
		for k > 0 {
			x := min(9, k)
			ans = append(ans, byte('0'+x))
			ans = append(ans, word[i])
			k -= x
		}
		i = j
	}
	return string(ans)
}

Try this approach in the editor

Approach 4: RegExp

TypeScript

function compressedString(word: string): string {
    const regex = /(.)\1{0,8}/g;
    let m: RegExpMatchArray | null = null;
    let res = '';

    while ((m = regex.exec(word))) {
        res += m[0].length + m[1];
    }

    return res;
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Iterative Counting Approach	Time Complexity: O(n), where n is the length of the string. Space Complexity: O(n), due to storing the result in a list.
Sliding Window Approach	Time Complexity: O(n), where n is the length of the string. Space Complexity: O(n), due to storing the result in pieces before joining them.
Two Pointers	–
RegExp	–

Complexity analysis

Approach	Time	Space	When to Use
Iterative Counting Approach	O(n)	O(1)	Best general solution. Simple single pass and easy to implement in interviews.
Sliding Window Approach	O(n)	O(1)	Useful when practicing two‑pointer or sliding window patterns on strings.

Frequently asked questions

Is String Compression III easy or hard?

String Compression III is classified as a Medium problem on LeetCode. The logic is straightforward once you recognize it as a run-length encoding variant, but handling the "maximum count of 9 per group" constraint adds a small twist.

String Compression III Python/Java solution

In Python or Java, iterate through the string while counting consecutive characters. When the count hits 9 or the character changes, append the count and character to a result builder (like a list in Python or StringBuilder in Java). This produces the compressed output in linear time.

How to solve String Compression III in O(n)?

Traverse the string and maintain a counter for consecutive identical characters. When the count reaches 9 or the character changes, append the compressed segment (count followed by the character) and reset the counter. This single-pass strategy guarantees O(n) time complexity.

What is the best approach for String Compression III?

The iterative counting approach is the most common solution. You scan the string once, count consecutive characters, and append "count + character" to the result whenever the count reaches 9 or the character changes. This achieves O(n) time complexity with constant auxiliary space.

Is String Compression III asked at Google/Amazon/Meta?

String compression and run-length encoding variations appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary slightly, the core idea of grouping consecutive characters and limiting counts is a common string-processing pattern.

What data structure is used in String Compression III?

The problem mainly uses basic string traversal and counters. No advanced data structures are required—just variables to track the current character and its frequency, plus a string builder or buffer for the compressed result.

What is the time complexity of String Compression III?

The optimal solution runs in O(n) time because each character in the string is processed exactly once. Both the iterative counting and sliding window approaches maintain a single pass over the input. Space complexity is O(1) excluding the output string.

String Compression III solution and explanation

The problem

Approach overview

Approach 1: Iterative Counting Approach

Approach 2: Sliding Window Approach

Approach 3: Two Pointers

Approach 4: RegExp

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

String Compression III solution and explanation

The problem

Approach overview

Approach 1: Iterative Counting Approach

Approach 2: Sliding Window Approach

Approach 3: Two Pointers

Approach 4: RegExp

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems