In this guide, you will get 3163. String Compression III LeetCode Solution with the best time and space complexity. The solution to String Compression III problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Given a string word, compress it using the following algorithm:
Begin with an empty string comp. While word is not empty, use the following operation:
Remove a maximum length prefix of word made of a single character c repeating at most 9 times.
Append the length of the prefix followed by 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.
For prefix “aaaaaaaaa”, append “9” followed by “a” to comp.
For prefix “aaaaa”, append “5” followed by “a” to comp.
For prefix “bb”, append “2” followed by “b” to comp.
Constraints:
1 <= word.length <= 2 * 105
word consists only of lowercase English letters.
3163. String Compression III LeetCode Solution in C++
class Solution {
public:
string compressedString(string word) {
const int n = word.length();
string ans;
for (int i = 0, j = 0; i < n; i = j) {
int count = 0;
while (j < n && word[j] == word[i] && count < 9) {
++j;
++count;
}
ans += to_string(count) + word[i];
}
return ans;
}
}; /* code provided by PROGIEZ */
3163. String Compression III LeetCode Solution in Java
class Solution {
public String compressedString(String word) {
final int n = word.length();
StringBuilder sb = new StringBuilder();
for (int i = 0, j = 0; i < n; i = j) {
int count = 0;
while (j < n && word.charAt(j) == word.charAt(i) && count < 9) {
++j;
++count;
}
sb.append(String.valueOf(count)).append(word.charAt(i));
}
return sb.toString();
}
} // code provided by PROGIEZ
3163. String Compression III LeetCode Solution in Python
class Solution:
def compressedString(self, word: str) -> str:
n = len(word)
ans = []
i = 0
j = 0
while i < n:
count = 0
while j < n and word[j] == word[i] and count < 9:
j += 1
count += 1
ans.append(str(count) + word[i])
i = j
return ''.join(ans) # code by PROGIEZ
