Scrabble – CodinGame solution in C
Count how many times each letter appears in your 7 tiles, then scan the dictionary once: a word is playable if, for every letter, it uses no more copies than you have. Score playable words with the Scrabble letter values and keep the best one with a strict greater-than comparison, so that on a tie the word that appears first in the dictionary wins.
The problem
You get a dictionary of up to 100,000 lowercase words (each at most 30 letters long) followed by the 7 letters you hold. Among the dictionary words you can actually spell with those letters, find the one worth the most points.
Each tile can be used only once, the letter values are the standard English Scrabble ones, and when several words reach the best score you must print the one that comes first in the given dictionary. There is always at least one valid word.
Approach, step by step
- Count the available lettersTurn the 7 tiles into an array of 26 counters. Duplicate tiles matter: with "aab" you can write "baa" but not "aaa".
- Check each word against the countersFor a dictionary word, increment a fresh array of 26 counters letter by letter and stop as soon as one counter exceeds what you have. Words longer than 7 letters can be rejected immediately.
- Score while you checkAdd the letter values in the same loop: 1 for e a i o n r t l s u, 2 for d g, 3 for b c m p, 4 for f h v w y, 5 for k, 8 for j x and 10 for q z.
- Keep the first best wordScan in dictionary order and replace the current best only when the new score is strictly greater. This automatically implements the tie rule without sorting.
Complexity
O(N * k)O(N * k)Each of the N words is examined once, letter by letter, with k <= 30, and the early rejection keeps the real cost close to 7 steps per word. Storing the dictionary is the only significant memory use; you could also process words as they are read.
Solution code
Bug fixed in this version: The original C code has memory errors. writeable() declares char copy[strlen(letters)] and then strcpy()s letters into it, which writes one byte past the end (it crashes with "buffer overflow detected" on a fortified build, even on the example input). Words are stored in char dictionary[N][30] although a word can be 30 letters long, which leaves no space for the terminating null byte, and the input is read with gets(), removed since C11. The replacement below fixes these with properly sized buffers and bounded scanf reads.
Scrabble – C
#include <stdio.h>
#include <string.h>
static const int POINTS[26] = {1,3,3,2,1,4,2,4,1,8,5,1,3,1,1,3,10,1,1,1,1,4,4,8,4,10};
static char words[100000][32];
int main(void) {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%31s", words[i]);
char letters[16];
scanf("%15s", letters);
int available[26] = {0};
for (int i = 0; letters[i]; i++)
available[letters[i] - 'a']++;
int best = -1, bestScore = -1;
for (int i = 0; i < n; i++) {
int used[26] = {0}, score = 0, ok = 1;
for (int j = 0; words[i][j] && ok; j++) {
int c = words[i][j] - 'a';
if (++used[c] > available[c]) ok = 0;
score += POINTS[c];
}
/* strict '>' keeps the first word of the dictionary on a tie */
if (ok && score > bestScore) {
bestScore = score;
best = i;
}
}
printf("%s\n", words[best]);
return 0;
}
Common mistakes
- Using a set instead of countsChecking only that every letter of the word appears among the tiles accepts "aaa" with tiles "abc". You must compare letter counts, not letter presence.
- Breaking ties the wrong wayUsing >= or sorting by score alone returns the last or an arbitrary best word. Only a strict > during a single scan in input order keeps the first one.
- Trailing newline in the lettersReading the tiles with fgets or a line-based reader can keep the newline, which then counts as a tile or breaks the index letter - 'a'. Strip it or read a whitespace-delimited token.
- Wrong letter valuesA single wrong value (k is 5, j and x are 8, q and z are 10) only shows up on the tests built around those letters. Double-check the table against the statement.
Going further
Because the rack has only 7 tiles, the dictionary size is the only thing that can make this slow, and the length filter is the cheapest optimisation: any word longer than 7 letters is rejected before looking at a single letter. A neat alternative representation is a multiset as a 26-digit vector: the word is playable when its vector is component-wise lower than or equal to the rack vector, which is what Python's Counter subtraction (not Counter(word) - Counter(rack)) expresses in one line. If you had to answer many different racks against the same dictionary, you would precompute each word's count vector once, and the classic trick for real word games is to index words by their sorted letters (an anagram key) so that all permutations are handled together.
FAQ
Can I use the same tile twice in Scrabble on CodinGame?
No. Each tile is used at most once, so a word with two "e" needs two "e" tiles. That is why you compare letter counts, not just letter presence.
What should I print when two words have the same score?
The one that appears first in the dictionary given as input. Scanning in order and replacing the best only on a strictly higher score does exactly that.
Do I need to worry about blank tiles or board bonuses?
No. There is no board and no joker: the score is just the sum of the letter values of the word.