DiverseFlowers | Topcoder Archive

Problem Statement

There are N flowers in a garden. Each flower has two properties: size (big or small) and color (red, green or blue). We will mark the type of a flower with one of six letters: R, G, B, r, g, b. For example, 'g' denotes a small green flower and 'B' denotes a big blue flower.

You will pick some flowers from the garden and arrange them into flower bouquets, each containing exactly K flowers. A bouquet must contain at least one flower of each color. A bouquet must also contain at least one flower of each size. And obviously, each individual flower can only be used in at most one bouquet.

Can you maximize the number of created bouquets?

You are given a String S with N characters that describe types of flowers in the garden. Return a String[] where each element represents one bouquet as a String with exactly K characters. If multiple solutions maximize the number of bouquets, return any of them. The order of bouquets doesn't matter, and neither does the order of flowers in a bouquet.

Definition

Class:: DiverseFlowers
Method:: solve
Parameters:: String, int
Returns:: String[]
Method signature:: String[] solve(String S, int K)
(be sure your method is public)

Constraints

S will contain exactly N characters.
N will be between 3 and 5000, inclusive.
K will be between 3 and N, inclusive.
Each character in S will be one of six: R, G, B, r, g, b.

Examples

```
"BBgbr"
```
```
3
```
```
Returns: {"Bgr" }
```
The only possible bouquet is "Bgr" (big blue, small green, small red) or any other permutation of these three characters. Note that chosen flowers don't have to be consecutive in the given String S.
```
"BBgbrGBBB"
```
```
3
```
```
Returns: {"rGB" }
```
Even though we have many more flowers in the garden this time, we still can create at most one bouquet.
```
"RGBrgb"
```
```
4
```
```
Returns: {"RBrg" }
```
Each bouquet must consist of 4 flowers. We can create only one bouquet, for example "RBrg" or "bRGB".

"RGBrgbRGBrgbRGBrgbRG"

Returns: {"RGBrg", "bRGBr", "gbRGB", "rgbRG" }

```
"rrrrrbbbbbbgR"
```
```
4
```
```
Returns: {"Rrbg" }
```
```
"gbgBgBgBbGGGBGGgbGBbGgGBBBBGGBGBbgBGBbbgGBBG"
```
```
3
```
```
Returns: { }
```
No bouquet will contain a red flower because there are no red flowers in the garden.

"RRgBrRRrgBRRBRgRRGBrRRgbRRRgBR"

Returns: {"RGbRR", "RgBRR", "RgBRR", "RgBRR", "RgBRr", "RgBrr" }

"RRgBrRRrgBRRBRgRRGBrRRgbRRRgBR"

Returns: {"RRgBrRRrgBRRBRgRRGBrRRgbRRRgBR" }

```
"RbRbGG"
```
```
3
```
```
Returns: {"RGb", "RGb" }
```

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.