Solution

Answer: 644997092988678

Let

$S={\texttt{A},\texttt{E},\texttt{F},\texttt{R}}$,
the keywords be

$$\texttt{FREE},\quad \texttt{FARE},\quad \texttt{AREA},\quad \texttt{REEF}.$$

We seek the number $f(30)$ of length-30 words over $S$ that contain each keyword exactly once.

1. Mathematical analysis

The problem is a classic finite-state dynamic programming problem.

The key observations are:

Every keyword has length $4$.
Whether appending a new character creates a keyword depends only on the last $3$ characters already written.
We must track which keywords have already appeared, because:

each keyword must appear at least once,
no keyword may appear more than once.

Thus the entire history of a word can be compressed into:

the current suffix of length at most $3$,
which of the four keywords have already occurred.

State representation

Define a DP state by:

$$(\text{suffix}, b)$$

where

suffix is the last at most 3 letters,
$b$ is a 4-bit mask recording which keywords have appeared.

For example:

bit 0 = FREE occurred,
bit 1 = FARE occurred,
bit 2 = AREA occurred,
bit 3 = REEF occurred.

There are only

$$1+4+4^2+4^3 = 85$$

possible suffixes, and only $2^4=16$ masks.

So the total state space is tiny:

$$85 \times 16 = 1360.$$

Transition rule

Suppose we are in state

$$(\text{suffix}, b)$$

and append a character $c\in S$.

Let

$$t = \text{suffix}+c.$$

Now:

if $t$ ends with one of the keywords, we detect it,
if that keyword was already seen before, this transition is invalid,
otherwise we set the corresponding bit in $b$.

The new suffix becomes the last 3 letters of $t$.

Why this works

A keyword has length 4, so when appending a new letter the only possible newly-created keyword is the suffix of length 4 ending at the new position.

Thus we never need to inspect older parts of the word.

This is exactly the standard automaton technique used for substring counting problems.

2. Python implementation

from collections import defaultdict

# The four keywords
keywords = ["FREE", "FARE", "AREA", "REEF"]

# Alphabet
letters = "AEFR"

def transition(suffix, ch):
    """
    Append character ch to the current suffix.
    Return:
        (new_suffix, list_of_keywords_completed)
    """
    t = suffix + ch

    found = []

    for i, k in enumerate(keywords):
        if t.endswith(k):
            found.append(i)

    # Keep only the last 3 characters
    new_suffix = t[-3:]

    return new_suffix, found

# DP[state] = number of ways
# state = (suffix, mask)
dp = defaultdict(int)

# Start with empty word
dp[("", 0)] = 1

N = 30

for _ in range(N):

    ndp = defaultdict(int)

    for (suffix, mask), ways in dp.items():

        for ch in letters:

            new_suffix, found = transition(suffix, ch)

            new_mask = mask
            valid = True

            # Every keyword must occur at most once
            for idx in found:

                bit = 1 << idx

                # keyword already used -> invalid
                if new_mask & bit:
                    valid = False
                    break

                new_mask |= bit

            if valid:
                ndp[(new_suffix, new_mask)] += ways

    dp = ndp

# all four keywords seen exactly once
FULL = (1 << 4) - 1

answer = sum(
    ways
    for (suffix, mask), ways in dp.items()
    if mask == FULL
)

print(answer)

3. Code walkthrough

Keywords and alphabet

keywords = ["FREE", "FARE", "AREA", "REEF"]
letters = "AEFR"

These define the problem exactly.

Transition function

def transition(suffix, ch):

We append one character.

t = suffix + ch

Since every keyword has length 4, we only need to test whether the new string ends with a keyword.

if t.endswith(k):

If yes, that keyword has just appeared.

Then we retain only the last 3 characters:

new_suffix = t[-3:]

because future matches depend only on them.

DP initialization

dp[("", 0)] = 1

The empty word has empty suffix and no keywords seen.

Main DP loop

For each length from $0$ to $30$:

for ch in letters:

try all 4 possible next letters.

If a keyword appears twice, reject:

if new_mask & bit:
    valid = False

Otherwise mark it as seen:

new_mask |= bit

Final extraction

The mask

FULL = 15

means all four keywords have appeared exactly once.

So we sum all states with mask $1111_2$.

4. Verification

The problem states:

$$f(9)=1$$

(the unique word is FREEFAREA).

Running the same program with $N=9$ gives exactly:

$$1.$$

The problem also gives:

$$f(15)=72863.$$

The program reproduces this value as well, strongly confirming correctness.

Finally, evaluating for $N=30$ yields:

$$644997092988678.$$

The magnitude is reasonable: the total number of length-30 words is

$$4^{30}\approx 1.15\times10^{18},$$

and our answer is a substantial but much smaller subset.

Answer: 644997092988678

Project Euler Problem 679