Longest Lexical Chain — Problem Statement & Solution Guide

StringsMediumMixed

TimeO(N·2^N)

SpaceO(N·2^N)

Quick Answer & Algorithm Key Takeaway

Use DFS with memoization on (lastWord, usedMask) to build the longest chain, updating the DP table in O(N·2^N) time and storing the smallest lexical sequence for equal lengths.

TopicStrings

PatternMixed

TimeO(N·2^N)

SpaceO(N·2^N)

Problem Description

Given an array of non‑empty lowercase strings words, construct a sequence of distinct strings that is as long as possible while satisfying the adjacency rule: the last character of each string must equal the first character of the next string. Return the sequence as a list. If more than one sequence attains the maximum length, output the lexicographically smallest one when the whole sequence is compared as a single space‑separated string. The input consists solely of the array words; the output is the chosen chain.

DSA Pattern Breakdown

"Longest Lexical Chain"

medium

WHY DOES IT MATTER?

The longest‑path‑with‑constraints pattern appears in many scheduling, routing, and game‑level design problems where you must maximize a sequence under adjacency rules; mastering it shows you can convert combinatorial constraints into tractable DP formulations.

OPTIMIZATION CHALLENGE

The key insight is to compress the exponential search space into a bitmask that uniquely identifies the set of used words, allowing memoization of sub‑problems. This reduces the naive factorial blow‑up to a manageable O(N·2^N) bound.

REAL-WORLD CONNECTION

Think of a package‑routing system where each hub can forward a parcel only to hubs whose names start with the letter the previous hub’s name ended with. Optimizing the longest possible delivery chain without revisiting a hub mirrors the lexical chain problem.

When coding, pre‑group words by their starting character to prune impossible transitions early, and always keep the chain as a list of indices – converting to strings only at the end – to keep the DP lightweight.

COMPLEXITY AT A GLANCE

⏱ Time:O(N·2^N)

💾 Space:O(N·2^N)

Core Theory — Why This Approach?

The problem can be modeled as a directed graph where each word is a node and there is an edge from word i to word j if the last character of i equals the first character of j. The task is to find the longest simple path – a sequence that never repeats a node – which is a classic NP‑hard problem on arbitrary graphs. A naïve exhaustive search that tries every permutation of words quickly explodes (O(N!)) and cannot handle N beyond 12‑15. The optimal paradigm leverages state‑compression DP (also called DP over subsets). By representing the set of already‑used words as a bitmask, we can memoize the best chain that ends with a particular word for each mask. The recurrence explores only feasible transitions (matching characters) and stores both length and the lexicographically smallest chain for ties, turning the exponential search into O(N·2^N) time while guaranteeing optimality for the given constraints.

Interview Questions on This Problem

Q1How would you model the adjacency rule of the Longest Lexical Chain problem using graph terminology, and why does this lead to an NP‑hard subproblem?

Treat each word as a vertex; draw a directed edge i→j when word i’s last character equals word j’s first character. Finding the longest sequence without reusing words is then the longest simple path problem, which is NP‑hard on general directed graphs.

Q2Explain how a bitmask DP can be used to solve the problem in O(N·2^N) time. What does each DP state represent?

DP[mask][last] stores the best chain (length and lexicographically smallest sequence) that uses exactly the words in ‘mask’ and ends with the word indexed by ‘last’. For each state we try to append any unused word whose first character matches the last character of the current word, updating the mask and last index. Memoization avoids recomputation.

Q3If two chains have the same maximum length, how do you ensure the returned chain is the lexicographically smallest overall?

When updating a DP state, compare the candidate chain with the existing one: first by length, then by lexicographic order of the whole sequence (element‑wise). Store the smaller one so that ties automatically propagate the minimal sequence up the recursion.

Examples

Example 1

Input

["apple","egg","giraffe","elephant","tiger","rat"]

Output

["apple","egg","giraffe","elephant","tiger","rat"]

Explanation: apple ends with 'e' → egg starts with 'e'; egg ends with 'g' → giraffe starts with 'g'; giraffe ends with 'e' → elephant starts with 'e'; elephant ends with 't' → tiger starts with 't'; tiger ends with 'r' → rat starts with 'r'. All six strings are distinct, giving the maximum possible length of 6.

Example 2

Input

["cat","taco","octopus","snake","elk","kangaroo"]

Output

["cat","taco","octopus","snake","elk","kangaroo"]

Explanation: cat→taco (c→t), taco→octopus (o→o), octopus→snake (s→s), snake→elk (e→e), elk→kangaroo (k→k). The chain uses every word exactly once, so its length 6 is optimal.

Example 3

Input

["dog","golf","fish","horse","eagle"]

Output

["fish","horse","eagle"]

Explanation: The longest feasible chain is fish→horse (f→h, fish ends with 'h'), horse→eagle (e→e). No other ordering yields more than three distinct words, so the returned chain has length 3.

Constraints

1 <= words.length <= 100000
1 <= each word length <= 20
All characters are lowercase English letters
Total number of characters across all words does not exceed 200000

Optimal Approach & Strategy

Use DFS with memoization on (lastWord, usedMask) to build the longest chain, updating the DP table in O(N·2^N) time and storing the smallest lexical sequence for equal lengths.

Brute Force Approach

Generate every permutation of the input, keep only those where adjacent words satisfy the character rule, and pick the longest (lexicographically smallest on ties).

Code Solutions

Language:

JavaScript Solution

Time: O(N·2^N)

/**
 * @param {string[]} words
 * @return {string[]}
 */
function longestLexicalChain(words) {
    if (words.length === 0) return [];
    
    // Sort words lexicographically
    const sortedWords = [...words].sort();
    
    // Build adjacency list
    const adj = new Map();
    for (const w of sortedWords) {
        adj.set(w, []);
    }
    
    for (const w of sortedWords) {
        const lastChar = w[w.length - 1];
        for (const next of sortedWords) {
            if (w !== next && next[0] === lastChar) {
                adj.get(w).push(next);
            }
        }
    }
    
    const memo = new Map();
    
    function dfs(current) {
        if (memo.has(current)) {
            return memo.get(current);
        }
        
        let maxLen = 1;
        let bestPath = [current];
        
        for (const next of adj.get(current)) {
            const [len, path] = dfs(next);
            if (len + 1 > maxLen || (len + 1 === maxLen && comparePaths(path, bestPath) < 0)) {
                maxLen = len + 1;
                bestPath = [current, ...path];
            }
        }
        
        memo.set(current, [maxLen, bestPath]);
        return [maxLen, bestPath];
    }
    
    function comparePaths(path1, path2) {
        for (let i = 0; i < Math.min(path1.length, path2.length); i++) {
            if (path1[i] < path2[i]) return -1;
            if (path1[i] > path2[i]) return 1;
        }
        return path1.length - path2.length;
    }
    
    let globalMaxLen = 0;
    let globalBestPath = [];
    
    for (const w of sortedWords) {
        const [len, path] = dfs(w);
        if (len > globalMaxLen || (len === globalMaxLen && comparePaths(path, globalBestPath) < 0)) {
            globalMaxLen = len;
            globalBestPath = path;
        }
    }
    
    return globalBestPath;
}

// Example usage
const words = ["apple", "egg", "giraffe", "elephant", "tiger", "rat"];
const result = longestLexicalChain(words);
console.log(result);

module.exports = longestLexicalChain;

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

class Solution {
private:
    vector<string> words;
    unordered_map<string, vector<string>> adj;
    unordered_map<string, pair<int, vector<string>>> memo;
    
    pair<int, vector<string>> dfs(string current) {
        if (memo.count(current)) {
            return memo[current];
        }
        
        int maxLen = 1;
        vector<string> bestPath = {current};
        
        for (const string& next : adj[current]) {
            auto [len, path] = dfs(next);
            if (len + 1 > maxLen || (len + 1 == maxLen && path < bestPath)) {
                maxLen = len + 1;
                bestPath = {current};
                bestPath.insert(bestPath.end(), path.begin(), path.end());
            }
        }
        
        memo[current] = {maxLen, bestPath};
        return memo[current];
    }

public:
    vector<string> longestLexicalChain(vector<string> words) {
        this->words = words;
        sort(words.begin(), words.end());
        
        // Build adjacency list
        for (const string& w : words) {
            char lastChar = w.back();
            for (const string& next : words) {
                if (w != next && next.front() == lastChar) {
                    adj[w].push_back(next);
                }
            }
        }
        
        int globalMaxLen = 0;
        vector<string> globalBestPath;
        
        for (const string& w : words) {
            auto [len, path] = dfs(w);
            if (len > globalMaxLen || (len == globalMaxLen && path < globalBestPath)) {
                globalMaxLen = len;
                globalBestPath = path;
            }
        }
        
        return globalBestPath;
    }
};

int main() {
    vector<string> words = {"apple", "egg", "giraffe", "elephant", "tiger", "rat"};
    Solution sol;
    vector<string> result = sol.longestLexicalChain(words);
    
    for (size_t i = 0; i < result.size(); ++i) {
        cout << result[i];
        if (i < result.size() - 1) cout << ", ";
    }
    cout << endl;
    
    return 0;
}

import java.util.*;

public class Solution {
    private List<String> words;
    private Map<String, List<String>> adj;
    private Map<String, int[]> memo;
    private Map<String, List<String>> pathMemo;
    
    public List<String> longestLexicalChain(List<String> words) {
        this.words = new ArrayList<>(words);
        Collections.sort(this.words);
        
        // Build adjacency list
        adj = new HashMap<>();
        for (String w : this.words) {
            adj.put(w, new ArrayList<>());
        }
        
        for (String w : this.words) {
            char lastChar = w.charAt(w.length() - 1);
            for (String next : this.words) {
                if (!w.equals(next) && next.charAt(0) == lastChar) {
                    adj.get(w).add(next);
                }
            }
        }
        
        memo = new HashMap<>();
        pathMemo = new HashMap<>();
        
        int globalMaxLen = 0;
        List<String> globalBestPath = new ArrayList<>();
        
        for (String w : this.words) {
            int[] result = dfs(w);
            List<String> path = pathMemo.get(w);
            if (result[0] > globalMaxLen || (result[0] == globalMaxLen && comparePaths(path, globalBestPath) < 0)) {
                globalMaxLen = result[0];
                globalBestPath = new ArrayList<>(path);
            }
        }
        
        return globalBestPath;
    }
    
    private int[] dfs(String current) {
        if (memo.containsKey(current)) {
            return memo.get(current);
        }
        
        int maxLen = 1;
        List<String> bestPath = new ArrayList<>();
        bestPath.add(current);
        
        for (String next : adj.get(current)) {
            int[] nextResult = dfs(next);
            List<String> nextPath = pathMemo.get(next);
            if (nextResult[0] + 1 > maxLen || (nextResult[0] + 1 == maxLen && comparePaths(nextPath, bestPath) < 0)) {
                maxLen = nextResult[0] + 1;
                bestPath = new ArrayList<>();
                bestPath.add(current);
                bestPath.addAll(nextPath);
            }
        }
        
        memo.put(current, new int[]{maxLen});
        pathMemo.put(current, new ArrayList<>(bestPath));
        return new int[]{maxLen};
    }
    
    private int comparePaths(List<String> path1, List<String> path2) {
        int minLen = Math.min(path1.size(), path2.size());
        for (int i = 0; i < minLen; i++) {
            int cmp = path1.get(i).compareTo(path2.get(i));
            if (cmp != 0) return cmp;
        }
        return path1.size() - path2.size();
    }
    
    public static void main(String[] args) {
        List<String> words = Arrays.asList("apple", "egg", "giraffe", "elephant", "tiger", "rat");
        Solution sol = new Solution();
        List<String> result = sol.longestLexicalChain(words);
        System.out.println(result);
    }
}

from typing import List

def longest_lexical_chain(words: List[str]) -> List[str]:
    if not words:
        return []
    
    # Sort words lexicographically
    sorted_words = sorted(words)
    
    # Build adjacency list
    adj = {w: [] for w in sorted_words}
    for w in sorted_words:
        last_char = w[-1]
        for next_w in sorted_words:
            if w != next_w and next_w[0] == last_char:
                adj[w].append(next_w)
    
    memo = {}
    
    def dfs(current: str) -> tuple:
        if current in memo:
            return memo[current]
        
        max_len = 1
        best_path = [current]
        
        for next_w in adj[current]:
            length, path = dfs(next_w)
            if length + 1 > max_len or (length + 1 == max_len and path < best_path):
                max_len = length + 1
                best_path = [current] + path
        
        memo[current] = (max_len, best_path)
        return max_len, best_path
    
    global_max_len = 0
    global_best_path = []
    
    for w in sorted_words:
        length, path = dfs(w)
        if length > global_max_len or (length == global_max_len and path < global_best_path):
            global_max_len = length
            global_best_path = path
    
    return global_best_path

if __name__ == "__main__":
    words = ["apple", "egg", "giraffe", "elephant", "tiger", "rat"]
    result = longest_lexical_chain(words)
    print(result)

/**
 * @param {string[]} words
 * @return {string[]}
 */
function longestLexicalChain(words) {
    if (words.length === 0) return [];
    
    // Sort words lexicographically
    const sortedWords = [...words].sort();
    
    // Build adjacency list
    const adj = new Map();
    for (const w of sortedWords) {
        adj.set(w, []);
    }
    
    for (const w of sortedWords) {
        const lastChar = w[w.length - 1];
        for (const next of sortedWords) {
            if (w !== next && next[0] === lastChar) {
                adj.get(w).push(next);
            }
        }
    }
    
    const memo = new Map();
    
    function dfs(current) {
        if (memo.has(current)) {
            return memo.get(current);
        }
        
        let maxLen = 1;
        let bestPath = [current];
        
        for (const next of adj.get(current)) {
            const [len, path] = dfs(next);
            if (len + 1 > maxLen || (len + 1 === maxLen && comparePaths(path, bestPath) < 0)) {
                maxLen = len + 1;
                bestPath = [current, ...path];
            }
        }
        
        memo.set(current, [maxLen, bestPath]);
        return [maxLen, bestPath];
    }
    
    function comparePaths(path1, path2) {
        for (let i = 0; i < Math.min(path1.length, path2.length); i++) {
            if (path1[i] < path2[i]) return -1;
            if (path1[i] > path2[i]) return 1;
        }
        return path1.length - path2.length;
    }
    
    let globalMaxLen = 0;
    let globalBestPath = [];
    
    for (const w of sortedWords) {
        const [len, path] = dfs(w);
        if (len > globalMaxLen || (len === globalMaxLen && comparePaths(path, globalBestPath) < 0)) {
            globalMaxLen = len;
            globalBestPath = path;
        }
    }
    
    return globalBestPath;
}

// Example usage
const words = ["apple", "egg", "giraffe", "elephant", "tiger", "rat"];
const result = longestLexicalChain(words);
console.log(result);

module.exports = longestLexicalChain;

Asked in Top Tech Interviews

SwiggyInfosys

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.