Maximum Score Words Formed by Letters

Hard
1329.

Maximum Score Words Formed by Letters

Maximum Score Words Formed by Letters is a hard coding problem on arrays, strings and backtracking, asked in Amazon and Google interviews.

You are given a list of words, a pool of letters (each entry is a single lowercase letter; letters may repeat) and an array score of length 26, where score[0] is the value of 'a', score[1] the value of 'b', and so on.

Choose any set of the words — each word at most once — that can be spelled together from the pool, where every letter tile is used at most once. The score of the set is the sum of the values of all letters in the chosen words.

Return the maximum score of any valid set (the empty set scores 0). You do not have to use every letter.

Example 1

Input
words = ["code","kairo","ode"], letters = ["c","o","d","e","k","a","i","r","o"], score = [1,0,3,2,1,0,0,0,1,0,5,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0]
Output
16
Explanation
"code" (7) and "kairo" (9) use the two `o` tiles between them. "code" and "ode" would need two `d` tiles.

Example 2

Input
words = ["xyz"], letters = ["x","y"], score = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
Output
0

Example 3

Input
words = ["aa","a"], letters = ["a","a","a"], score = [4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
Output
12

Constraints

  • 1 <= words.length <= 14
  • 1 <= words[i].length <= 15
  • 1 <= letters.length <= 100
  • letters[i].length == 1
  • score.length == 26
  • 0 <= score[i] <= 10
  • words[i] and letters[i] contain only lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} words
 * @param {string[]} letters
 * @param {number[]} score
 * @return {number}
 */
var maxScoreWords = function(words, letters, score) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Score Words Formed by Letters — Problem & Solution

Maximum Score Words Formed by Letters solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Maximum Score Words Formed by Letters is a hard coding problem on arrays, strings and backtracking, asked in Amazon and Google interviews.

Problem statement

You are given a list of words, a pool of letters (each entry is a single lowercase letter; letters may repeat) and an array score of length 26, where score[0] is the value of 'a', score[1] the value of 'b', and so on.

Choose any set of the words — each word at most once — that can be spelled together from the pool, where every letter tile is used at most once. The score of the set is the sum of the values of all letters in the chosen words.

Return the maximum score of any valid set (the empty set scores 0). You do not have to use every letter.

Example 1

Input: words = ["code","kairo","ode"], letters = ["c","o","d","e","k","a","i","r","o"], score = [1,0,3,2,1,0,0,0,1,0,5,0,0,0,1,0,0,1,0,0,0,0,0,0,0,0]
Output: 16
Explanation: "code" (7) and "kairo" (9) use the two `o` tiles between them. "code" and "ode" would need two `d` tiles.

Example 2

Input: words = ["xyz"], letters = ["x","y"], score = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
Output: 0

Example 3

Input: words = ["aa","a"], letters = ["a","a","a"], score = [4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
Output: 12

Constraints

  • 1 <= words.length <= 14
  • 1 <= words[i].length <= 15
  • 1 <= letters.length <= 100
  • letters[i].length == 1
  • score.length == 26
  • 0 <= score[i] <= 10
  • words[i] and letters[i] contain only lowercase English letters

Hints for Maximum Score Words Formed by Letters

  1. Hint 1

    With at most 14 words there are at most 2^14 subsets — few enough to try them all.

  2. Hint 2

    Keep a count of the tiles still available; a word can be added only if the counts cover it.

  3. Hint 3

    Backtrack word by word: skip it, or (if it fits) subtract its letters, recurse, and add them back.

How to solve Maximum Score Words Formed by Letters

The word list is tiny, so search every subset by backtracking, carrying the remaining tile counts and pruning any branch that would overdraw a letter.

Approach

  1. Count the available tiles per letter and precompute each word's value.
  2. dfs(i) returns the best score using words i..n-1: first try skipping word i.
  3. Then subtract word i's letters from the counts; if no count went negative, try value[i] + dfs(i + 1).
  4. Restore the counts and return the better of the two options.

Why it works

Every subset of words corresponds to one root-to-leaf path of take/skip decisions, and a subset is valid exactly when no letter count ever goes negative along its path. So the recursion examines every valid subset and nothing else, and returns the largest score among them.

Complexity

  • Time — O(2^n · L), L = total word length
  • Space — O(n + 26)

Pitfalls

  • Restore the counts even when the word did not fit, since they were already decremented.
  • A word may repeat a letter ("aa"), so it needs as many tiles as occurrences.
  • Choosing words greedily by value fails — two medium words can beat one expensive word that blocks them.

Reference solution

Python

from typing import List

def maxScoreWords(words: List[str], letters: List[str], score: List[int]) -> int:
    have = [0] * 26
    for ch in letters:
        have[ord(ch) - 97] += 1
    codes = [[ord(ch) - 97 for ch in w] for w in words]
    worth = [sum(score[c] for c in cs) for cs in codes]
    n = len(words)

    def dfs(i):
        if i == n:
            return 0
        best = dfs(i + 1)
        cs = codes[i]
        for c in cs:
            have[c] -= 1
        if all(have[c] >= 0 for c in cs):
            best = max(best, worth[i] + dfs(i + 1))
        for c in cs:
            have[c] += 1
        return best

    return dfs(0)

Java

public static int maxScoreWords(String[] words, String[] letters, int[] score) {
    int[] have = new int[26];
    for (String l : letters) have[l.charAt(0) - 'a']++;
    int n = words.length;
    int[] worth = new int[n];
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < words[i].length(); k++) worth[i] += score[words[i].charAt(k) - 'a'];
    }
    return mswDfs(words, worth, have, 0);
}

static int mswDfs(String[] words, int[] worth, int[] have, int i) {
    if (i == words.length) return 0;
    int best = mswDfs(words, worth, have, i + 1);
    String w = words[i];
    boolean ok = true;
    for (int k = 0; k < w.length(); k++) have[w.charAt(k) - 'a']--;
    for (int k = 0; k < w.length(); k++) if (have[w.charAt(k) - 'a'] < 0) ok = false;
    if (ok) best = Math.max(best, worth[i] + mswDfs(words, worth, have, i + 1));
    for (int k = 0; k < w.length(); k++) have[w.charAt(k) - 'a']++;
    return best;
}

C++

static int mswDfs(const vector<string>& words, const vector<int>& worth, vector<int>& have, int i) {
    if (i == (int)words.size()) return 0;
    int best = mswDfs(words, worth, have, i + 1);
    const string& w = words[i];
    bool ok = true;
    for (char ch : w) have[ch - 'a']--;
    for (char ch : w) if (have[ch - 'a'] < 0) ok = false;
    if (ok) best = max(best, worth[i] + mswDfs(words, worth, have, i + 1));
    for (char ch : w) have[ch - 'a']++;
    return best;
}

int maxScoreWords(vector<string>& words, vector<string>& letters, vector<int>& score) {
    vector<int> have(26, 0);
    for (const string& l : letters) have[l[0] - 'a']++;
    vector<int> worth(words.size(), 0);
    for (size_t i = 0; i < words.size(); i++) {
        for (char ch : words[i]) worth[i] += score[ch - 'a'];
    }
    return mswDfs(words, worth, have, 0);
}

JavaScript

var maxScoreWords = function(words, letters, score) {
    var have = new Array(26).fill(0);
    for (var i = 0; i < letters.length; i++) have[letters[i].charCodeAt(0) - 97]++;
    var codes = words.map(function(w) {
        var cs = [];
        for (var k = 0; k < w.length; k++) cs.push(w.charCodeAt(k) - 97);
        return cs;
    });
    var worth = codes.map(function(cs) {
        var s = 0;
        for (var k = 0; k < cs.length; k++) s += score[cs[k]];
        return s;
    });
    function dfs(i) {
        if (i === words.length) return 0;
        var best = dfs(i + 1);
        var cs = codes[i], ok = true, k;
        for (k = 0; k < cs.length; k++) have[cs[k]]--;
        for (k = 0; k < cs.length; k++) if (have[cs[k]] < 0) ok = false;
        if (ok) best = Math.max(best, worth[i] + dfs(i + 1));
        for (k = 0; k < cs.length; k++) have[cs[k]]++;
        return best;
    }
    return dfs(0);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings