Encode the Message
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".

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

Question

Encode the Message

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".

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

Accepted Answer

Steps:
1) Sort all the words in descending order of their lengths.
2) Initialise res with first word in the vector + "#"
3) Now we just need to find, if other words in the vector + # are substring of res or not. if not, append that word to res.

Accepted Answer

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'.

Space Complexity: O(n)Explanation:

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.

Time Complexity: O(n)Explanation:

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.

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".

Input format:

Note:

Output format:

Note:

Constraints :

Top Walmart Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Walmart Software Developer