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.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), as it constructs the output string.
| 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. |
String Compression • Kevin Naughton Jr. • 97,097 views views
Watch 9 more video solutions →Practice String Compression III with our built-in code editor and test cases.
Practice on FleetCode