Compress the String — Asked in Amazon and Microsoft Interview

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

1. 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.
2. Start moving the endIndex to every character till the character at startIndex is a match.
3. 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)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.