The word chain problem involves constructing the longest possilbe sequence ("dragon") from a given set of words, starting with a specified character. Each word may be used at most twice in the chain. When two words are joined, overlapping parts are merged into one—e.g., beast and astonish form beastonish. Importantly, no word in the chain can fully contain another adjacent word.

Input Format

• The first line contains an integer n (≤20), the number of words.
• The next n lines each contain a single word.
• The last line is a single character indicating the required starting letter of the dragon.

Output Format

Output the maximum possible length of such a dragon.

Example

5
at
touch
cheat
choose
tact
a

Output:

23

One valid chain is: atoucheatactactouchoose.

Solution Approach

This problem is solved using depth-first search (DFS) with backtracking. Preprocessing computes the maximum overlap between every pair of words where the suffix of the first matches the prefix of the second, without full containment. During DFS, we track usage counts (max 2 per word) and accumulate total length by subtracting overlaps when appending words.

Reference Implementation

#include <bits/stdc++.h>
using namespace std;

int n, maxLen = 0;
string words[25];
int used[25];
int overlap[25][25];

// Compute maximum valid overlap from end of a to start of b
int computeOverlap(const string& a, const string& b) {
    int lenA = a.size(), lenB = b.size();
    for (int i = 1; i < min(lenA, lenB); ++i) {
        if (a.substr(lenA - i) == b.substr(0, i))
            return i;
    }
    return 0;
}

void dfs(int current, int currentLen) {
    maxLen = max(maxLen, currentLen);
    for (int i = 0; i < n; ++i) {
        if (used[i] >= 2 || overlap[current][i] == 0) continue;
        used[i]++;
        dfs(i, currentLen + (int)words[i].size() - overlap[current][i]);
        used[i]--;
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> words[i];
    string startChar;
    cin >> startChar;

    // Precompute overlaps
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            overlap[i][j] = computeOverlap(words[i], words[j]);

    // Try all words starting with the given character
    for (int i = 0; i < n; ++i) {
        if (words[i][0] != startChar[0]) continue;
        used[i] = 1;
        dfs(i, words[i].size());
        used[i] = 0;
    }

    cout << maxLen << endl;
    return 0;
}