String Compression III - Video Solutions

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.