String Compression III - Solution & Explanation
Problem Statement
Given a string word, compress it using the following algorithm:
- Begin with an empty string
comp. Whilewordis not empty, use the following operation:- Remove a maximum length prefix of
wordmade of a single charactercrepeating at most 9 times. - Append the length of the prefix followed by
ctocomp.
- Remove a maximum length prefix of
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"tocomp. - For prefix
"aaaaa", append"5"followed by"a"tocomp. - For prefix
"bb", append"2"followed by"b"tocomp.
Constraints:
1 <= word.length <= 2 * 105wordconsists 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.
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.
Complexity
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), as we store the result string separately.
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.
This C solution uses two indices, start and end, to define a window over the string where characters are counted. Once the window reaches the maximum size or a different character is encountered, it appends to the result.
Complexity
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), as it constructs the output string.
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
Code
Python
Java
C++
Go
TypeScript
JavaScript
Approach 4: RegExp
Code
TypeScript
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Iterative Counting Approach | Time Complexity: O(n), where n is the length of the string. |
| Sliding Window Approach | Time Complexity: O(n), where n is the length of the string. |
| Two Pointers | — |
| RegExp | — |
Detailed 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. |
Video Solution
String Compression III | Simple Simulation | Leetcode 3163 | codestorywithMIK • codestorywithMIK • 6,250 views views
Watch 9 more video solutions →Frequently Asked Questions
Is String Compression III easy or hard?
String Compression III Python/Java solution
How to solve String Compression III in O(n)?
What is the best approach for String Compression III?
Is String Compression III asked at Google/Amazon/Meta?
What data structure is used in String Compression III?
What is the time complexity of String Compression III?
Ready to solve this problem?
Practice String Compression III with our built-in code editor and test cases.
Practice on FleetCode