Bob and his special string

★★★★★

5 votes

Binary Search, , Algorithms

Details

Submissions

Discussion

Editorial

Problem

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$ .

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

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.