Compress the String

Moderate

0/80

Average time to solve is 32m

Contributed by

40 upvotes

Asked in companies

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.

Example:

If a string has 'x' repeated 5 times, replace this "xxxxx" with "x5".
The string is compressed only when the repeated character count is more than 1.

Note:

Consecutive count of every character in the input string is less than or equal to 9. You are not required to print anything. It has already been taken care of. Just implement the given function and return the compressed string.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first and only line of input contains a string without any leading and trailing spaces.

Output Format:

The output contains the string after compression printed in single line

Constraints:

0 <= N <= 10^6

Where 'N' is the length of the input string.

Time Limit: 1 sec

Sample Input 1:

aaabbccdsa

Sample Output 1:

a3b2c2dsa

Explanation for Sample Output 1:

In the given string 'a' is repeated 3 times, 'b' is repeated 2 times, 'c' is repeated 2 times and 'd', 's' and 'a' and occuring 1 time hence no compression for last 3 characters.

Sample Input 2:

aaabbcddeeeee

Sample Output 2:

a3b2cd2e5

Explanation for Sample Output 2:

In the given string 'a' is repeated 3 times, 'b' is repeated 2 times, 'c' is occuring single time, 'd' is repeating 2 times and 'e' is repeating 5times.

Hint 1

It is mentioned that we only need to consider characters that are consecutively repeated more than once. We may use this information to solve this problem.

Approaches (1)

Approach 1

Frequency Calculation Approach

The steps are as follows:

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. If the frequency of the character is 1, no need to append its frequency.
Move the ‘STARTINDEX' to ‘ENDINDEX’.
Repeat until all the characters are traversed in this manner.

Time Complexity

O(N), Where ‘N' is the total number of characters or length of the string.

Since we iterate through all the characters once. Thus the time complexity will be O(N).

Space Complexity

O(1)

Since we use constant space. Thus the space complexity will be O(1).

(100% EXP penalty)

Compress the String

Console