A florist is arranging a bouquet described by a string of lowercase letters, where each letter names the bloom type placed at that position (so the same letter appearing at different positions means the same bloom type repeated). To keep the arrangement's palette curated, the florist wants the bouquet to contain at most k distinct bloom types. The florist achieves this by removing individual flowers one at a time; removing a flower removes only that single occurrence, and a bloom type disappears from the arrangement only once every one of its occurrences has been removed. Given the bouquet and the target k, find the minimum number of flowers that must be removed so that the remaining flowers span at most k distinct bloom types.
The first line contains a string s of lowercase English letters describing the bouquet. The second line contains a single integer k.
A single integer: the minimum number of flowers that must be removed.
Example 1
Input
tree 2
Expected
1
Explanation
The bouquet has bloom types t (1 flower), r (1 flower), and e (2 flowers) -- 3 distinct types, but only 2 are allowed. The cheapest type to eliminate entirely is either singleton t or r, costing just 1 flower and leaving 2 distinct types. Minimum removals = 1.
Example 2
Input
aabbcc 1
Expected
4
Explanation
Bloom types a (2), b (2), and c (2) give 3 distinct types, but only 1 is allowed, so 2 of the three types must be eliminated entirely. Eliminating any two of the three equal-sized types costs 2+2=4 flowers. Minimum removals = 4.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →