ColorfulChocolates | Topcoder Archive

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 an int 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.

Definition

Class:: ColorfulChocolates
Method:: maximumSpread
Parameters:: String, int
Returns:: int
Method signature:: int maximumSpread(String chocolates, int maxSwaps)
(be sure your method is public)

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

```
"ABCDCBC"
```
```
1
```
```
Returns: 2
```
One optimal solution is to swap chocolates at positions 2 and 3, obtaining the row "ABDCCBC", which has spread 2.
```
"ABCDCBC"
```
```
2
```
```
Returns: 3
```
The only optimal solution is to produce the row "ABDCCCB".
```
"ABBABABBA"
```
```
3
```
```
Returns: 4
```
The row "ABBBBAABA" can be produced with 3 swaps.
```
"ABBABABBA"
```
```
4
```
```
Returns: 5
```
An optimal solution is to produce the row "AABBBBBAA".

"QASOKZNHWNFODOQNHGQKGLIHTPJUVGKLHFZTGPDCEKSJYIWFOO"

Returns: 5

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.