0810HardArrayHash TableStringDynamic ProgrammingBacktrackingBit ManipulationCountingBitmask

Best Tile Rack Play

Tracked in this browser only

Trains the technique from

LeetCode 1255Maximum Score Words Formed by Letters

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a 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)

The intended approach

Time O(2^w * (w + L + 26)) for w candidates of length at most L: each subset copies a tally, folds in one word, checks 26 letters against the rack and adds up its members' points.Space O(2^w) letter tallies of 26 counters each.

With at most fourteen candidates there are at most 2^14 possible plays, so every subset is examined. Walking the subsets in increasing numeric order means the subset with its lowest member removed has already been handled, so its letter tally is copied and the one extra word folded into it, which keeps the per-subset work to one word rather than the whole set. A subset is playable when no letter's tally exceeds the count of that letter on the rack; when a smaller part already exceeded the rack the larger one is marked unplayable without any comparison. The best score over playable subsets wins, starting from zero for the empty play.

Pythonentry point: best_rack_score

def best_rack_score(candidates, rack, value):
    # A play is just a subset of the candidate list, and there are at most 2^14
    # of those, so every subset is examined. Subsets are visited in increasing
    # numeric order, which means the subset without its lowest member has always
    # been costed already: its letter tally is copied and the one extra word is
    # folded in. A subset whose smaller part already outran the rack cannot come
    # back, so its tally is never even compared.
    #
    # Time: O(2^w * (w + L + 26)) for w candidates of length at most L: per
    # subset one letter tally is copied, one word folded in, the rack checked,
    # and the subset's points added up over its members.
    # Space: O(2^w) tallies of 26 counters.
    have = [0] * 26
    for ch in rack:
        have[ord(ch) - 97] += 1

    words = []
    for w in candidates:
        pts = 0
        for ch in w:
            pts += value[ord(ch) - 97]
        words.append((w, pts))

    size = len(candidates)
    tally = [None] * (1 << size)
    tally[0] = [0] * 26
    fits = [True] * (1 << size)
    best = 0
    for mask in range(1, 1 << size):
        low = mask & -mask
        idx = low.bit_length() - 1
        rest = mask ^ low
        base = tally[rest]
        cur = base[:]
        word, pts = words[idx]
        for ch in word:
            cur[ord(ch) - 97] += 1
        tally[mask] = cur
        if not fits[rest]:
            fits[mask] = False
            continue
        ok = True
        for k in range(26):
            if cur[k] > have[k]:
                ok = False
                break
        fits[mask] = ok
        if not ok:
            continue
        total = pts
        rem = rest
        while rem:
            bit = rem & -rem
            total += words[bit.bit_length() - 1][1]
            rem ^= bit
        if total > best:
            best = total
    return best

The obvious version

Enumerate combinations of the candidate list by size, pile the letters of each combination into a counter, keep the combinations whose counter is covered by the rack's counter, and score them letter by letter. Rebuilds every tally from scratch.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_best_rack_score(candidates, rack, value):
    """Every combination of candidates, checked with letter counters."""
    from collections import Counter
    from itertools import combinations

    pool = Counter(rack)
    best = 0
    spots = range(len(candidates))
    for size in range(1, len(candidates) + 1):
        for combo in combinations(spots, size):
            need = Counter()
            for i in combo:
                need.update(candidates[i])
            if all(need[ch] <= pool[ch] for ch in need):
                pts = 0
                for ch, cnt in need.items():
                    pts += value[ord(ch) - 97] * cnt
                if pts > best:
                    best = pts
    return best

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in