Last Updated: 13 Apr, 2021

Ninja And Rearrange String

Moderate

Asked in company

Solve now

Problem statement

Ninja has been given a string ‘STR’ and an integer ‘D’. Ninja has to rearrange the string ‘STR’ such that the same characters are present at least ‘D’ distance from each other.

If it is possible to rearrange the string ‘STR’, then return true; otherwise, print false.

Note :

The string ‘STR’ contains only lowercase alphabet characters.

For example :

If ‘STR’ = “aaadbbcc” and ‘D’ = 2.
Then one of the possible solution is “abacabcd”.

Input Format :

The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain two single space-separated integers ‘N’ and ‘D’ which denote the size of the ‘STR’ and the distance such that the same characters are present at least ‘D’ distance from each other, respectively.

The next line of each test case contains the string ‘STR’.

Output Format :

For each test case, print "true" if it is possible to rearrange the string ‘STR’, otherwise, print "false" without quotes.

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

Note :

You don’t need to print anything; it has already been taken care of. Just implement the given function.

Constraints :

1 <= ‘T’ <= 50
1 <= ‘N’ <= 10000
1 <= ‘D’ <= 26
‘STR’ = {a - z}

Time limit: 1 sec

Solve now

Approaches

01 Approach

The basic idea is to first store all the characters of this ‘STR’ in a HashMap. Then iterate over this HashMap, store these key-value pairs in a max-heap and sort according to the frequency of these characters.

Then Iterate over this heap and greedily remove the top different ‘D’ characters from the heap and store them in a resultant string.

The steps are as follows:

Declare a HashMap ‘freq’ as we discussed above.
Declare a variable ‘len’ and store the length of the ‘STR’.
Run a loop to the length of this string ‘STR’:
- Add the current character into the HashMap ‘freq’.
Declare a max-heap ‘allCharFreqPairs’ as we discussed above.
Iterate through the HashMap ‘freq’:
- Add current key-value pair in max-heap ‘allCharFreqPairs’.
Declare an empty string ‘ANS’.
While max-heap is not equal to empty:
- Declare a list/vector ‘temp’.
- ‘smallDis’ = min( ‘ D’ , ‘len’).
- Run a loop ‘i’ = 0 to ‘smallDis’:
  - If max-heap is empty:
    - Return false.
  - Remove the top element from the max-heap.
  - Store this character in the string ‘ANS’.
  - Subtract the frequency by 1 and add in array/vector ‘temp’.
  - ‘len’ = ‘len’ - 1.
- Add all values of array/vector ‘temp’ into max-heap.
Finally, return true.

Solve now