Compress a string of alphabetic characters with the basic encoding where you simply count the number of repeated characters.
Character “A” is repeated 5 times consecutively.
Character “a” is repeated 3 times consecutively, character “C” is repeated 2 times consecutively.
Input Parameters: One string parameter.
Output: Return the compressed string.
• Input string consists of alphabetic characters only
• 1 <= length of the string <= 10^5
We provided one solution for this problem, it is optimal.
The problem asks to encode the input string in such a way so that its length remains the same or decreases. To do so, we counted repeated consecutive characters. If the count was more than one, we replaced the repeated portion by a number followed by the character.
O(n) where n denotes the length of the input string.
O(1) because no extra memory was used.