Register for our webinar

How to Nail your next Technical Interview

1 hour
Loading...
1
Enter details
2
Select webinar slot
*Invalid First Name
*Invalid Last Name
*Invalid Phone Number
By sharing your contact details, you agree to our privacy policy.
Select your webinar time
Step 1
Step 2
Congratulations!
You have registered for our webinar
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
Step 1
Step 2
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.
About usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar
Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career

String Compression Problem

Compress a string of alphabetic characters with the basic encoding where you simply count the number of repeated characters.

Example One

Input: AAAAA

Output: 5A

Character “A” is repeated 5 times consecutively.

Example Two

Input: ABaaaBCC

Output: AB3aB2C

Character “a” is repeated 3 times consecutively, character “C” is repeated 2 times consecutively.

Notes

Input Parameters: One string parameter.

Output: Return the compressed string.

Constraints:

• Input string consists of alphabetic characters only

• 1

Solution

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.

Time complexity:

O(n) where n denotes the length of the input string.

Auxiliary space:

O(1) because no extra memory was used.

Space complexity:

O(n).

Try yourself in the Editor

Note: Input and Output will already be taken care of.

Recommended Posts

All Posts