Last Updated: 21 Aug, 2021

Ninja and The Magical Sword

Moderate

Asked in company

Solve now

Problem statement

Ninja is very fond of strings so he is creating a new type of string, help him in creating his new magical string.

You are given a string ‘S’ of length |S| and an integer ‘N’. Now, you need to find a string 'STR' of length at most ‘N’ such that if you add this string ‘X’ number of times(STR + STR +... X times) let's say it as 'XSTR' then the frequency of each character in 'XSTR' string should be greater than or equal to the frequency of the same character in the string ‘S’. 'XSTR' should cover all the characters of string S.

Help Ninja in finding the minimum possible value of ‘X’.

For example:

Given S = "aaabbc" and N = 4.
Frequency of each character is 'a' = 3, 'b' = 2, and 'c' = 1.

If we take ‘STR’ = "aabc" and add this 2 times i.e "aabcaabc" the frequency of each character will be 'a' = 4, 'b' = 2, 'c' = 2. Here the frequency of each character is greater or equal to that of string ‘S’. i.e for 'a' 4 >= 3, 'b' 2 >= 2 and 'c' 2 >= 1.
Hence X = 2.
We can't find any other string 'STR' of length N such that X < 2.

Input Format :

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

The first line contains an integer ‘N’ representing the maximum length of string that ninja can write.

The second line contains a string ‘S’ representing the given string.

Output Format :

For each test case, return an integer denoting the minimum possible value of 'X'.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.
It is guaranteed that the solution will always exist.

Constraints :

1 <= T <= 10
1 <= N <= 10^5
1 <= |S| <= 10^5

where 'S' only contains lowercase letters i.e a-z.
The total number of distinct characters in 'S' is always less than equal to N.

Time Limit: 1 sec

Solve now

Approaches

01 Approach

In this approach, we will find the minimum possible value of ‘N’ given a fixed number of sheets.

Let ‘X’ denotes the minimum number of times we need to repeat ‘STR’.

If a character repeats ‘P’ times in the ‘S’ then it must appear ceil(P / X) times in ‘STR’, Thus we will get the minimum possible value of ‘N’ by summing the ceil value of each character.

Now we check for every value of ‘X’ from 1 to S.length()(we are taking S.length() as even in worst case i.e. all characters equal and ‘N’ = 1 maximum possible answer is S.length()) if that give less ‘N’ then this is the required one then we will return that value.

Algorithm:

Declare an array ‘FREQ’ of size 26 to store the freq of each character.
Iterate through the given string ‘S’ and add +1 when a character is encounter to its corresponding position.
For ‘i’ : 1 to S.length().
- if(isPoss(i, FREQ, N)
  - return i;

Function for checking the minimum possible value of ‘N’ IS_POSS(MID, FREQ, N)

Declare a variable ‘SUM’ := 0
Iterate all values of ‘FREQ’ and add Ceil(FREQ[i]/MID) in ‘SUM’
Return true if ‘SUM’ <= ‘N’ else return false.

Solve now

02 Approach

In this approach, we will just optimise the previous approach by apply binary search on the value of ‘X’ instead of checking all values.

Algorithm:

Declare an array ‘FREQ’ of size 26 to store the freq of each character.
Iterate through the given string ‘S’ and add +1 when a character is encounter to its corresponding position.
Declare variables ‘L’ := 0, ‘R’ := S.length(), ‘MID’ := 0, ‘ANS’ := S.length()
while( ‘L’ < ‘R’ )
- if(IS_POSS(MID, FREQ, N)){
  - ‘R’ = ‘MID - 1’,
  - ‘ANS’ = min(‘ANS’, ‘MID’)
- Else
  - ‘L’ = ‘MID + 1’
Return ‘ANS’

Function for checking the minimum possible value of ‘N’ IS_POSS(MID, FREQ, N)

Declare a variable ‘SUM’ := 0
Iterate all values of ‘FREQ’ and add Ceil(FREQ[i]/MID) in ‘SUM’
Return true if ‘SUM’ <= ‘N’ else return false.

Solve now