Encode the Message

Easy

0/40

Average time to solve is 18m

103 upvotes

Asked in companies

Problem statement

You have been given a text message. You have to return the Run-length Encoding of the given message.

Run-length encoding is a fast and simple method of encoding strings. The basic idea is to represent repeated successive characters as the character and a single count. For example, the string "aaaabbbccdaa" would be encoded as "a4b3c2d1a2".

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

Input format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow:

The first and only line of each test case will contain a string denoting the message.

Note:

It's guaranteed that the message string will have no digits and consists solely of lowercase alphabetic characters.

Output format:

For each test case, print a single line containing the encoded message string. 

Output for every test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 100000

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

Time Limit: 1 sec

Sample Input 1 :

3
aabbc
abcd
abbdcaas

Sample Output 1 :

a2b2c1
a1b1c1d1
a1b2d1c1a2s1

Explaination for Sample Input 1:

Test Case 1: As 2 consecutive 'a', 2 consecutive 'b', and 1 'c' are present in the given string so output is "a2b2c1".

Test Case 2: As 1 consecutive 'a', 1 consecutive 'b', 1 consecutive 'c' and 1 consecutive 'd' are present in the given string so output is "a1b1c1d1".

Test Case 3: As 1 consecutive 'a', 2 consecutive 'b', 1 consecutive 'd', 1consecutive 'c', 2 consecutive 'a' and 1 consecutive 's' are present in the given string so output is "a1b2d1c1a2s1".

Sample Input 2:

2
sadasd
adsad

Sample Output 2:

s1a1d1a1s1d1
a1d1s1a1d1

Hint 1

Can you build the encoded string by iterating left to right counting repeated successive characters in the message string?

Approaches (1)

Approach 1

Constructive Implementation

Build the encoded string by iterating left to right counting repeated successive characters

Create an empty encoded string 'ENCODEDMESSAGE' = “”.
Iterate from i = 0 to N - 1 where ‘N’ is the length of the 'MESSAGE' string.
Store the current character in 'CURCHAR' = 'MESSAGE'[i] and initialize the 'CHARFREQ' = 1.
Increase ‘i’ and 'CHARFREQ' while i + 1 < N and s[i + 1] == 'CURCHAR'. This will count the repeated successive characters.
Append the 'CURCHAR' and 'CHARFREQ' (as string) in 'ENCODEDMESSAGE'.
Return the 'ENCODEDMESSAGE'.

Time Complexity

O(N), where ‘N’ is the length of the ‘MESSAGE’ string.

As we are just iterating from left to right once in ‘MESSAGE’ string building the encoded string.

Space Complexity

O(N), where ‘N’ is the length of the ‘MESSAGE’ string.

As we can have the length of the encoded string 2 * N in the worst case where every neighbouring character is different.

(100% EXP penalty)

Encode the Message

Console