Given a string word, compress it using the following algorithm:
comp. While word is not empty, use the following operation:
word made of a single character c repeating at most 9 times.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.
"aaaaaaaaa", append "9" followed by "a" to comp."aaaaa", append "5" followed by "a" to comp."bb", append "2" followed by "b" to comp.
Constraints:
1 <= word.length <= 2 * 105word consists only of lowercase English letters.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.
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.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), as we store the result string separately.
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.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), as it constructs the output string.
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
Python
Java
C++
Go
TypeScript
JavaScript
TypeScript
JavaScript
| 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 | — |
| 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. |
String Compression III | Simple Simulation | Leetcode 3163 | codestorywithMIK • codestorywithMIK • 6,085 views views
Watch 9 more video solutions →Practice String Compression III with our built-in code editor and test cases.
Practice on FleetCode