Bob is very fond of strings so he is creating a new type of string. Help him in creating his new special string.
You are given a string \(s\) of length \(|s|\) and an integer \(n\). Now, you are required 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 us say it is \(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 Bob in finding the minimum possible value of \(x\).
Input format
- The first line contains an integer \(n\) representing the maximum length of string that Bob can write.
- The second line contains a string \(s\) representing the given string.
Output format
Print an integer denoting the minimum possible value of \(x\).
Constraints
\(2 \le n \le 10^5\)
\(1\le|s|\le 10^5\)
where \(s\) only contains lowercase letters, that is, \(a-z\)
The total number of distinct characters in \(s\) is always less than or equal to \(n\).
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.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor