Istr
SRM 684 · 2016-03-02 · by subscriber
SRM 684 · 2016-03-02 · by subscriber · Brute Force, Simulation
Problem Statement
Problem Statement
Hero came up with an interesting way to calculate the value of any string.
It works as follows:
String s and an int k.
You are allowed to remove at most k characters from s.
Your goal is to produce a string with the smallest possible value.
Compute and return that value.
- Find all distinct characters that appear in the string.
- For each of those characters, count the number of occurrences.
- Square each of those counts.
- Sum all those squares to get the value of the string.
For example, suppose Hero has the string "abacaba". This string contains 4 'a's, 2 'b's, and 1 'c'. Thus, its value is 4*4 + 2*2 + 1*1 = 21.
You are given aConstraints
- s will contain between 1 and 50 characters, inclusive.
- Each character in s will be a lowercase letter ('a'-'z').
- k will be between 0 and the length of s, inclusive.
Examples
0)
"aba" 1 Returns: 2
The optimal strategy is to erase one of the two 'a's. This produces a string with value 1*1 + 1*1 = 2.
1)
"abacaba" 0 Returns: 21
2)
"abacaba" 1 Returns: 14
3)
"abacaba" 3 Returns: 6
4)
"abc" 3 Returns: 0
Submissions are judged against all 205 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class Istr with a public method int count(string s, int k) · 205 test cases · 2 s / 256 MB per case