Coding Solution

Scrabble – CodinGame solution in C

Mediumletter countingstring processinglinear searchhash mapUpdated
Short answer

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

  1. 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".
  2. 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.
  3. 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.
  4. 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

TimeO(N * k)
SpaceO(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

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.

Similar puzzles

★ 5.0 · 16 reviews · 928 users Add to Chrome