Problem Statement :
Write a program to do basic string compression. For a character which is consecutively repeated more than once, replace consecutive duplicate occurrences with the count of repetitions.
Sample Input:
aaabbccdsa
Sample Output:
a3b2c2dsa
Approach :
Frequency Calculation Approach
- Keep two indices, both starting from the initial character. Let’s say, ‘startIndex’ and ‘endIndex’. These indices are going to tell the start and end of the substring where the characters are the same.
- Start moving the endIndex to every character till the character at startIndex is a match.
- Whenever there is a mismatch, we can calculate the frequency of the character at the startIndex by subtracting the startIndex from endIndex. Append the character at the startIndex with its total frequency and add it to the final string you want to return.
Note: if the frequency of the character is 1, no need to append its frequency.
4. Move the startIndex to endIndex
5. Repeat until all the characters are traversed in this manner.
Time Complexity — O(N)
Space Complexity — O(1)