Show problems as
Classic problem #1255HardArrayHash TableStringDynamic ProgrammingBacktrackingBit ManipulationCountingBitmask

Maximum Score Words Formed by Letters

Real-world version: Best Tile Rack Play
Tracked in this browser only
Read Maximum Score Words Formed by Letters on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

You are holding a rack of letter tiles and looking at a list of words you are allowed to play.

rack lists the tiles you hold, one lowercase letter per entry, and the same letter may appear on several tiles. candidates lists the words on offer; you may play any set of them, each word at most once, and words may be played in any order. Playing a word spends one tile for each letter of that word, and a tile spent on one word cannot be spent again on another, so the words you play must be spelled out of your rack all together.

value has 26 entries: value[0] is the points a played 'a' tile is worth, value[1] the points for 'b', and so on to value[25] for 'z'. The score of a play is the total points of every tile it spends.

Return the highest score you can reach. Playing nothing is allowed and scores 0.

Examples

Example 1

Input
candidates = ["pear", "plum", "ripe"], rack = ["p", "e", "a", "r", "p", "l", "u", "m"], value = [2, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 4, 5, 0, 0, 3, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0]
Output
21

Playing "pear" and "plum" together spends the tiles p, e, a, r, p, l, u, m, which is exactly the rack. Those tiles are worth 3 + 1 + 2 + 2 + 3 + 4 + 1 + 5 = 21 points. The word "ripe" needs an i tile and the rack holds none.

Example 2

Input
candidates = ["abcd", "abc", "ad"], rack = ["a", "a", "b", "c", "d"], value = [1, 2, 3, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Output
17

Playing "abc" and "ad" spends a, b, c and a, d, which the rack covers. The score is 1 + 2 + 3 + 1 + 10 = 17.

Example 3

Input
candidates = ["zebra"], rack = ["z", "e", "b", "r"], value = [1, 3, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 10]
Output
0

The only word on offer needs an a tile and the rack holds none, so nothing can be played and the score is 0.

Constraints

  • 1 <= candidates.length <= 14
  • 1 <= candidates[i].length <= 15
  • 1 <= rack.length <= 100
  • rack[i].length == 1
  • value.length == 26
  • 0 <= value[i] <= 10
  • candidates[i] and rack[i] hold lowercase English letters only.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def best_rack_score(candidates: list[str], rack: list[str], value: list[int]) -> int:
Java
public int bestRackScore(String[] candidates, char[] rack, int[] value)

More on the same topics