Thursday, March 12, 2015

[Flipkart Interview] Compress the string

Given a string you are provided with the possible operations.
We can group the adjacent substrings, for e.g ABCABCBC can be compressed as
2ABC1BC or 1ABCA2BC

Among all the possible options, task is to find the resultant string with the minimum length.


In case if there are multiple solutions return the lexicographically smallest string.
So for the above example the solution would be 2ABC1BC

Another example would be
FLFLAFLAFLAF
Solution: 1FLF3LAF



Approach:


One obvious approach is to find all the possible compressions of the string and then find the one with the minimum length.

So how do you achieve this? We need to find the repetitive substrings in sequence and perform it recursively. Well it is an awful exponential algorithm.


So how do we improve this ?

No comments :

Post a Comment