Sponsored
Sponsored
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.
1#include <string>
std::string compressString(const std::string& word) {
std::string result;
int i = 0;
while (i < word.length()) {
char current = word[i];
int count = 0;
while (i < word.length() && word[i] == current && count < 9) {
++i;
++count;
}
result += std::to_string(count) + current;
}
return result;
}
int main() {
std::cout << compressString("abcde") << std::endl;
std::cout << compressString("aaaaaaaaaaaaaabb") << std::endl;
return 0;
}This C++ solution uses an iterative approach with a while-loop to construct the compressed string, using the std::string class.
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#include <stdio.h>
2#include <string.h>
3
4void compressString(const char* word) {
5 int length = strlen(word);
6 char result[length * 2 + 1];
7 int index = 0, start = 0;
8 while (start < length) {
9 char current = word[start];
10 int end = start;
11 while (end < length && word[end] == current && end - start < 9) {
12 ++end;
13 }
14 int count = end - start;
15 result[index++] = '0' + count;
16 result[index++] = current;
17 start = end;
18 }
19 result[index] = '\0';
20 printf("%s\n", result);
21}
22
23int main() {
24 compressString("abcde");
25 compressString("aaaaaaaaaaaaaabb");
26 return 0;
27}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.