Last Updated: 12 Apr, 2021
Ninja's Favourite String
Moderate
Asked in company
Some time ago, Ninja found an entertaining string ‘S’ consisting of only lowercase English letters. But he did not like the string if two same characters are not ‘K’ distant apart.
He wants your help to know whether it is possible to rearrange the string’s characters such that all two similar characters are at least ‘K’ distance apart.
Return 1 if it is possible to make such string else return 0.
For example: Let ‘S’ = “aabc” and ‘K’ = 1, then we need to rearrange ‘S’ as two ‘a’ are not ‘K’ distance apart, after rearranging we can write “abac” or “abca” and return 1.
Input Format :
The first line of input contains an integer 'T' representing the number of test cases.
The first line of each test case contains a single integer ‘K’ denoting the distance between the same characters.
The second line of each test case contains a string ‘S’.
Output Format :
For each test case, print an integer 1 if it is possible to arrange the string else print 0.
The output for each test case is printed in a separate line.
Constraints :
1 <= T <= 5
1 <= N <= 5000
1 <= K <= N
Where ‘N’ is the length of the string ‘S’.
Time limit: 1 sec
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Approaches
The idea here is to store each character’s next possible position in the map and then find for each index which characters among ‘a’ to ‘z’ will have the highest frequency and the next possible condition is less than this index. If we are unable to find any candidate for this then we return 0.
Algorithm:
- Declare a map ‘FREQ’ to store frequencies of each character and ‘NEXTPOS’ to store next possible position.
- for(i : 0 -> ‘S’.length)
- ‘FREQ’[‘S’[i]]++
- for( i : 0 -> ‘S’.length )
- int ‘CAND’ = findNextCharacter(i, ‘FREQ’, ‘NEXTPOS’)
- if we can’t find a candidate then return 0.
- else
- Add the ‘CAND’ to the ‘RES’ string.
- return 1
Description of ‘findNextCharacter’ function
The function will take three parameters:
- Index: An integer to keep track of current index of the string.
- Freq: An map to keep track of the remaining frequencies of each character.
- Nextpos: an map to keep track of the next possible position of all characters.
int findNextCharacter( ‘INDEX’, ‘FREQ’ , ‘NEXTPOS’ )
- ‘MAX’ := integer.min and ‘CAND’ := -1
- for( i : a -> z)
- if ( FREQ[i] is greater than 0 and MAX and INDEX > NEXTPOS[i] )
- then MAX := FREQ[i] and CAND = i
- if ( FREQ[i] is greater than 0 and MAX and INDEX > NEXTPOS[i] )
- return cand.
The idea here is to store all the frequency of the character and place the most frequent one first as close as possible, to extract out the character based on maximum frequency, we will be using max-heap (implemented using priority queue).
Algorithm:
- Declare a map ‘MP’ of char, int and an empty string to store the final ‘RESULT’= “”.
- Traverse the string
- for(i : 0 -> S.length):
- MP[S[i]] ++.
- for(i : 0 -> S.length):
- Declare a maxHeap to store all frequencies with corresponding characters and a variable ‘LEN’ = S.length.
- while(!maxheap.empty)
- Declare an array ‘ARR’ of pair to store the changes
- Declare a variable CNT= min(K, LEN)
- for( i : 0 -> CNT):
- If maxHeap.empty return 0
- t = maxHeap.top. maxHeap.pop
- RESULT += t.second
- if( --t.first > 0 ) arr.push_back(t)
- Len--;
- Push the elements of ‘ARR’ back in maxHeap.
- Return 1.