tiles.java

/*
 You are given:
- a set of tiles, each tile represents a letter and a score associated with it; there might be many tiles of the same letter, each having the same score
- a dictionary of valid words

Find a set of words combined from the tiles that will give you a max sum score. Each tile can be used at most once.
You have to subtract the total sum of remaining (unused) tiles from the result.
*/

class Tile {
  char letter;
  int weight;
}

public int findMax(List<Tile> tiles, List<String> words) {
  // Build maps for fast lookup
  Map<Character, Integer> weights = new HashMap<>();
  Map<Character, Integer> counts = new HashMap<>();
  for (Tile tile : tiles) {
    if (weights.containsKey(tile.letter)) {
      counts.put(tile.letter, counts.get(tile.letter) + 1);
    } else {
      weights.put(tile.letter, tile.weight);
      counts.put(tile.letter, 1);
    }
  }
  
  // Run recursive search
  return findMax(weights, counts, words, 0, 0);
}

private int findMax(Map<Character, Integer> weights, Map<Character, Integer> counts, List<String> words, int wordIndex, int currentSum) {
  if (wordIndex == words.size()) {
    // we've reached the end - calculate the final sum
    return currentSum - remainingSum(weights, counts);
  }
  
  String word = words.get(wordIndex);
  boolean can = canMakeWord(counts, word);
  
  // Option 1: include the word in the result
  int sum1 = Integer.MIN_VALUE;
  if (can) {
    // Remove tiles making the word
    makeWord(counts, word);
    
    // Move to the next word
    sum1 = findMax(weights, counts, words, wordIndex + 1, currentSum + wordSum(weights, word));
    
    // Add tiles back (restore)
    removeWord(counts, word);
  }

  // Option 2: skip the word - just move the index
  int sum2 = findMax(weights, counts, words, wordIndex + 1, currentSum);
  
  return Math.max(sum1, sum2);
}

private int remainingSum(Map<Character, Integer> weights, Map<Character, Integer> counts) {
  int sum = 0;
  for (Map.Entry w : weights.entrySet()) {
    sum += w.getValue() * counts.get(w.getKey());
  }
  return sum;
}

private boolean canMakeWord(Map<Character, Integer> counts, String word) {
  Map<Character, Integer> wordCounts = new HashMap<>();
  for (int i=0; i<word.length(); i++) {
    char c = word.charAt(i);
    if (wordCounts.containsKey(c)) {
      wordCounts.put(c, wordCounts.get(c) + 1);
    } else {
      wordCounts.put(c, 1);
    }
    Integer actualCount = counts.get(c);
    if (actualCount == null) {
      return false; // the letter is not present
    }
    if (actualCount < wordCounts.get(c)) {
      return false; // not enough repeats of a letter
    }
  }
  return true;
}

private void makeWord(Map<Character, Integer> counts, String word) {
  for (int i=0; i<word.length(); i++) {
    char c = word.charAt(i);
    counts.put(c, counts.get(c) - 1);
  }
}

private void removeWord(Map<Character, Integer> counts, String word) {
  for (int i=0; i<word.length(); i++) {
    char c = word.charAt(i);
    counts.put(c, counts.get(c) + 1);
  }
}

private int wordSum(Map<Character, Integer> weights, String word) {
  int sum = 0;
  for (int i=0; i<word.length(); i++) {
    char c = word.charAt(i);
    sum += weights.get(c);
  }
  return sum;
}