String Compression III | Simple Simulation | Leetcode 3163 | codestorywithMIK
String Compression III - Video Solution
Watch 10 video solutions for String Compression III, a medium level problem involving String. This walkthrough by codestorywithMIK has 6,250 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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. |