ColorfulChocolates
SRM 551 · 2012-06-05 · by bloops
SRM 551 · 2012-06-05 · by bloops · Greedy
Problem Statement
Problem Statement
Beaver Bindu has some chocolates arranged in a row.
The wrapping of each chocolate has a single color.
Multiple chocolates can share the same color.
In this problem, each of the possible colors is represented by an uppercase letter.
You are given a String chocolates.
For each i, the i-th chocolate (0-based index) in the row has the color chocolates[i].
The spread of a row of chocolates is the maximum number of adjacent chocolates that all share the same color. Formally, the spread can be defined as the maximum value of (j-i+1), where i <= j and all the chocolates in the positions between i and j, inclusive, have the same color.
You are also given anint maxSwaps.
Bindu can swap any two adjacent chocolates.
She has decided to make at most maxSwaps such swaps.
Return the maximum spread she can obtain.
The spread of a row of chocolates is the maximum number of adjacent chocolates that all share the same color. Formally, the spread can be defined as the maximum value of (j-i+1), where i <= j and all the chocolates in the positions between i and j, inclusive, have the same color.
You are also given an
Return the maximum spread she can obtain.
Constraints
- chocolates will contain between 1 and 50 characters, inclusive.
- Each character in chocolates will be an uppercase letter ('A'-'Z').
- maxSwaps will be between 1 and 2500, inclusive.
Examples
0)
"ABCDCBC" 1 Returns: 2
One optimal solution is to swap chocolates at positions 2 and 3, obtaining the row "ABDCCBC", which has spread 2.
1)
"ABCDCBC" 2 Returns: 3
The only optimal solution is to produce the row "ABDCCCB".
2)
"ABBABABBA" 3 Returns: 4
The row "ABBBBAABA" can be produced with 3 swaps.
3)
"ABBABABBA" 4 Returns: 5
An optimal solution is to produce the row "AABBBBBAA".
4)
"QASOKZNHWNFODOQNHGQKGLIHTPJUVGKLHFZTGPDCEKSJYIWFOO" 77 Returns: 5
Submissions are judged against all 100 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ColorfulChocolates with a public method int maximumSpread(string chocolates, int maxSwaps) · 100 test cases · 2 s / 256 MB per case