Variant 13.9.2 : Given an array A, rearrange the elements so that the shortest subarray containing all the distinct values in A has maximum possible length

**twedkghksf** · October 8, 2015, 4:02am

Does anyone know how to go about solving this problem? Thanks.

**tsunghsienlee** · October 13, 2015, 4:49am

The key idea (or hint) is thinking about partition. After partition, you will get a rearranged array where elements with identical values are group together. Then, you might think about how to make this with maximum possible length.

**twedkghksf** · October 14, 2015, 2:58am

Thanks! After this step, my idea is to get the element with the least duplicates and move it as well is its duplicates to one end of the array. Then do the same for the element with the second least number of duplicates and move them to the other end of the array. Is there a better way to go about it? Thanks again!

**tsunghsienlee** · October 14, 2015, 4:56am

I think you got the answer

**abhishall** · June 25, 2020, 5:20pm

@twedkghksf Could you please help me understand your approach for this example:

(Consider the String as an array of characters)

A = “abcbadcaeaabe”

For this, the frequency map is:
a -> 5
b -> 3
c -> 2
d -> 1
e -> 2

So following your approach, we would place d at the end, then e and so on…
Resulting in aaaaabbbcceed, in which the shortest subarray containing all distinct values is: abbbcceed ( length = 9)

But if we arranged the array as: dccaaaaabbbee, the shortest subarray containing all distinct characters is the entire array except the last element, which is dccaaaaabbbe (length = 12) and longer than previous one.

Am I doing something wrong here ?

**preparer** · November 29, 2020, 2:40am

The approach that was suggested is to put the least frequent item (and its duplicates) in one end, and the next less frequent item on the other end and so on. So using your example it is going to be: deeaaaaabbcc which has a max window length of 11.