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

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 ?

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