Maximum score words formed by letters

Array Hash Table String Dynamic Programming Backtracking Bit Manipulation Counting Bitmask

81.5% acceptance

Feb 25, 2026

1846

119

Given a list of words, list of single letters (might be repeating) and score of every character. Return the maximum score of any valid set of words formed by using the given letters (words[i] cannot be used two or more times). It is not necessary to use all characters in letters and each letter can only be used once. Score of letters 'a', 'b', 'c', ... ,'z' is given by score[0], score[1], ... , score[25] respectively.

Solution

Rust

Time O(n³)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_score_words(words: Vec<String>, letters: Vec<char>, score: Vec<i32>) -> i32 {
    let n = words.len();
    let mut available = [0i32; 26];
    for c in &letters {
      available[(*c as u8 - b'a') as usize] += 1;
    }

    // Precompute word char counts and scores
    let word_data: Vec<([i32; 26], i32)> = words.iter().map(|w| {
      let mut cnt = [0i32; 26];
      let mut s = 0;
      for c in w.bytes() {
        let idx = (c - b'a') as usize;
        cnt[idx] += 1;
        s += score[idx];
      }
      (cnt, s)
    }).collect();

    let mut ans = 0;
    for mask in 0u32..(1u32 << n) {
      let mut used = [0i32; 26];
      let mut total_score = 0;
      let mut valid = true;

      for i in 0..n {
        if mask & (1 << i) != 0 {
          for j in 0..26 {
            used[j] += word_data[i].0[j];
          }
          total_score += word_data[i].1;
        }
      }

      for j in 0..26 {
        if used[j] > available[j] {
          valid = false;
          break;
        }
      }

      if valid {
        ans = ans.max(total_score);
      }
    }
    ans
  }
}