BeautifulBanner | Topcoder Archive

Problem Statement

You are so excited about coming to TechOlympics that you've decided to prepare a huge and beautiful banner with "TechOlympics" written on it. However, there is a little problem: you're not really good at drawing. Fortunately, there is a little shop nearby that sells nice individual paper letters. So your plan is to go to the shop, buy proper letters, and glue them onto a sheet of paper to form the word "TechOlympics".

There are N letters currently available in the shop. They are described by the String letters and the int[] beauty. For each i, 0 &lt= i < N-1, there is one letter given by the i-th character of letters and its beauty value is beauty[i].

The beauty value of the banner is the sum of beauty values of individual letters used for the banner. Return the maximum beauty value of a "TechOlympics" banner that you can create from the given letters. If no banner can be created, return -1 instead. Note that lowercase and uppercase letters are considered different in this problem.

Definition

Class:: BeautifulBanner
Method:: maximumBeauty
Parameters:: String, int[]
Returns:: int
Method signature:: int maximumBeauty(String letters, int[] beauty)
(be sure your method is public)

Constraints

letters will contain between 10 and 50 characters, inclusive.
Each character in letters will be a lowercase letter ('a'-'z') or an uppercase letter ('A'-'Z').
beauty will contain the same number of elements as the number of characters in letters.
Each element of beauty will be between 0 and 100, inclusive.

Examples

```
"TechOlympics"
```
```
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
```
```
Returns: 78
```
We have no choice, the store has exactly the letters we need to create the banner.
```
"eychlTmpOics"
```
```
{5, 3, 1, 7, 3, 2, 5, 3, 5, 7, 1, 3}
```
```
Returns: 45
```
This store has the same letters as in Example 0, they are just presented in a different order and have different costs.
```
"techolympics"
```
```
{12, 11, 10, 8, 9, 7, 6, 5, 4, 3, 2, 1}
```
```
Returns: -1
```
Lowercase and uppercase letters in this problem are considered to be distinct. Therefore there is not enough letters for the banner.
```
"TechOlympis"
```
```
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
```
```
Returns: -1
```
This store only has one letter 'c', but we need two for the banner.

"mcspypseseilmhTOOiciTys"

{68,69,9,45,66,50,11,41,42,
 54,21,61,74,2,62,40,1,3,
 49,21,2,54,50}

Returns: 598

"hNymOymymhlllTymcDlhmycpcccclyTTmTTTDlmOXpeOscliTt"

{31,10,25,51,47,29,23,17,37,51,24,15,6,23,43,22,48,40,
 5,9,38,8,1,43,32,36,38,32,28,36,4,26,4,5,32,24,43,52,
 6,25,23,40,5,43,42,10,31,23,24,40}

Returns: 475

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.