Ninja and The Magical Sword

Moderate
0/80
Average time to solve is 50m
profile
Contributed by
2 upvotes
Asked in company
Ola

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3
ababccb
4
aaaaaaa
Sample Output 1 :
3
2
Explanation of Sample Input 1 :
For the first test case, we will take ‘STR’ = ‘abc’ and X = 3. So we are ‘XSTR’ = “abcabcabc”.
For the second test case, we will take ‘STR’ = “aaaa” and X = 2. So we are ‘XSTR’ = “aaaaaaaa”.
Sample Input 2 :
2
5
ninja
6
superduper
Sample Output 2 :
1
2
Hint

Try to find the minimum length string require for ‘K’ scrolls.

Approaches (2)
Brute Force

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.
Time Complexity

O(K * 26), where ‘K’ is the minimum possible value of ‘X' that is the number of times we need to repeat string.

 

As we are checking the minimum possible length string for each possible value of ‘X’.

 

Space Complexity

O(1),

 

As we are storing only constant number of elements i.e. 26 for each alphabet.

Code Solution
(100% EXP penalty)
Ninja and The Magical Sword
Full screen
Console