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.In #3163 String Compression III, the goal is to compress a string by grouping consecutive identical characters and representing each group with its count followed by the character. A key constraint is that the count for a single group cannot exceed 9, so longer sequences must be split into multiple segments.
The most efficient strategy is a single-pass traversal. Iterate through the string while tracking the current character and its frequency. Whenever the character changes or the count reaches 9, append the current count and character to the result and reset the counter. This ensures that long runs are split properly while preserving order.
Using a StringBuilder (or similar mutable string structure) helps avoid repeated string concatenation costs. Since each character is processed once, the approach runs in linear time. The algorithm requires only a few extra variables besides the output structure, making it space efficient.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Single-pass string traversal with grouping | O(n) | O(n) for output |
Kevin Naughton Jr.
Use these hints if you're stuck. Try solving on your own first.
Each time, just cut the same character in prefix up to at max 9 times. It’s always better to cut a bigger prefix.
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.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), as we store the result string separately.
1using System;
2
3class StringCompressor {
4 public static string CompressString(string word) {
5 System.Text.StringBuilder result = new System.Text.StringBuilder();
6 int i = 0;
7 while (i < word.Length) {
8 char current = word[i];
9 int count = 0;
10 while (i < word.Length && word[i] == current && count < 9) {
11 i++;
12 count++;
13 }
14 result.Append(count).Append(current);
15 }
16 return result.ToString();
17 }
18
19 public static void Main(string[] args) {
20 Console.WriteLine(CompressString("abcde"));
21 Console.WriteLine(CompressString("aaaaaaaaaaaaaabb"));
22 }
23}This C# solution uses a StringBuilder to efficiently build the compressed string, iterating over the input with an index-based 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.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), as it constructs the output string.
1#
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Problems involving string compression and run-length encoding patterns are common in technical interviews. Variants of this problem test a candidate's ability to handle edge cases, string traversal, and efficient output construction.
A StringBuilder (or similar mutable string buffer) is ideal for building the compressed string efficiently. It avoids the overhead of repeated string concatenation and keeps the implementation simple during traversal.
The optimal approach is a single-pass traversal of the string while counting consecutive identical characters. Whenever the count reaches 9 or the character changes, append the count and character to the result. This ensures correct compression while maintaining O(n) time complexity.
The problem restricts each encoded segment to a maximum count of 9. If a sequence exceeds 9 identical characters, it must be split into multiple compressed parts, each with its own count and character representation.
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.