StringCutter | Topcoder Archive

Problem Statement

You are given a String s on which you must perform a series of cuts. Your ideal goal is for each of the resulting parts to consist of only equal letters. For example, you would want to cut the string "aaabbacc" into four parts: "aaa" + "bb" + a" + "cc". However, cutting is a costly operation, and you are not allowed to exceed a total cost of maxCost.

A single cut separates a string into two parts (left and right). The cost of such a cut is the string length of the shorter part. You must perform the cuts in such a way that minimizes the total penalty of the resulting parts. The penalty of a single part is equal to D squared, where D is the number of distinct letters contained in that part minus 1. For example, if you cut "aaabbacc" into "aaab" + "bacc", the total penalty would be (2-1)^2 + (3-1)^2 = 5.

Return the minimum possible penalty you can achieve while not exceeding a total cost of maxCost.

Definition

Class:: StringCutter
Method:: minPenalty
Parameters:: String, int
Returns:: int
Method signature:: int minPenalty(String s, int maxCost)
(be sure your method is public)

Constraints

s will contain between 1 and 50 characters, inclusive.
s will contain only lowercase letters ('a'-'z').
maxCost will be between 1 and 50, inclusive.

Examples

```
"aaabbacc"
```
```
2
```
```
Returns: 1
```
One way to get the smallest penalty is to make one cut that separates the last 2 characters from the rest of the string.
```
"aabbbbcc"
```
```
4
```
```
Returns: 0
```
```
"abcdefgh"
```
```
6
```
```
Returns: 1
```
```
"abcdefghgfedcba"
```
```
1
```
```
Returns: 49
```
```
"aaaaabbbbbcccc"
```
```
4
```
```
Returns: 1
```

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.