Ninja's Favourite String

Moderate
0/80
Average time to solve is 25m
4 upvotes
Asked in company
Uber

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1 :
2
1
aabbcc
2
abcccd
Sample Output 1 :
1
1
Explanation of Sample Output 1 :
Test Case 1: We can rearrange “aabbcc” as “cbacba” all the same characters are at least one distance apart and return 1. 

Test Case 2:  We can rearrange “abcccd” as “cdcbca” all the same characters are at least 2 distance apart and return 1.
Sample Input 2 :
2
3
aaacccb
2
aaczcbcab
Sample Output 2 :
0
1
Hint

Try to find which character will be placed at a particular place.

Approaches (2)
Brute force

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
  • return cand.
Time Complexity

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

 

We are iterating all characters (O(N)) and storing their frequencies. We are then finding the best suitable candidate for each position in O(26).
So overall complexity is O(N * 26) or we can say O(N).

Space Complexity

O(1).

 

The total number of distinct characters is 26 (constant), and we are storing their frequencies, so space complexity is O(1).

Code Solution
(100% EXP penalty)
Ninja's Favourite String
Full screen
Console