Ninja And Rearrange String

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
4 upvotes
Asked in company
CIS - Cyber Infrastructure

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”.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
6 2
abcdef
9 2
aaaabbbcc
Sample Output 1 :
true
true
Explanation of sample input 1 :
In the first test case, all characters are different so any permutation of this string is our answer i,e “abcdef”, “abcdfe”, and so on. As it is possible to rearrange the given string as described in the problem, we return true.

In the second test case, the possible answer is “abcabcaba”.
Sample Input 2 :
2
4 3
aabb
6 2
aabbcc
Sample Output 2 :
false
true
Explanation of sample input 2 :
In the first test case, it is not possible to rearrange the string ‘STR’. So we return false.

In the second test case,  one of the possible answers is “abcabc”, ”bacabc” and so on. As it is possible to rearrange the given string as described in the problem, we return true.
Hint

Can you think of storing the characters with their freq in a heap?

Approaches (1)
Heap

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:

 

  1. Declare a HashMap ‘freq’ as we discussed above.
  2. Declare a variable ‘len’ and store the length of the ‘STR’.
  3. Run a loop to the length of this string ‘STR’:
    • Add the current character into the HashMap ‘freq’.
  4. Declare a max-heap ‘allCharFreqPairs’ as we discussed above.
  5. Iterate through the HashMap ‘freq’:
    • Add current key-value pair in max-heap ‘allCharFreqPairs’.
  6. Declare an empty string ‘ANS’.
  7. 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.
  8. Finally, return true.
Time Complexity

O(N), where ‘N’ is the length of the string ‘STR’.

 

Because first, we are adding all the characters of the ‘STR’ into HashMap that takes O(N) time. Then we are iterating over the HashMap and storing all key-value pairs into a min-heap. As the unique characters will go up to only 26 and so, this takes constant work mainly. Then we are iterating over max-heap and storing all characters into a string ‘ANS’ that also takes O(N) time. So, the overall time complexity is O(N).

Space Complexity

O(N), where ‘N’ is the length of the string ‘STR’.

 

Because first, we are adding all the characters of the ‘STR’ into HashMap. Then we are iterating over the HashMap and storing all key-value pairs into a max-heap. Then we are iterating over the max-heap and storing all characters into a string ‘ANS’. so, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Ninja And Rearrange String
Full screen
Console