Longest Lexical Chain — Problem Statement & Solution Guide
Problem Description
Given a list of strings, find the longest sequence of strings where each string starts with the last character of the previous string. If multiple sequences have the same maximum length, return the lexicographically smallest one.
Examples
Input
['apple', 'pleasure', 'asure', 'apple', 'pleasure', 'asure']
Output
['apple', 'pleasure', 'asure']
Explanation: Step-by-step: 1. Start with 'apple'. 2. 'apple' ends with 'e', so we look for a string starting with 'e'. 3. We find 'pleasure' which ends with 'e'. 4. 'pleasure' ends with 'e', so we look for a string starting with 'e'. 5. We find 'asure' which ends with 'e'. 6. The longest sequence is ['apple', 'pleasure', 'asure']
Input
['hello','llama','llama','llama']
Output
['hello','llama','llama','llama']
Explanation: Step-by-step: 1. Start with 'hello'. 2. 'hello' ends with 'o', so we look for a string starting with 'o'. 3. We cannot find any string starting with 'o', so we stop here. 4. The longest sequence is ['hello','llama','llama','llama']
Constraints
- The length of the input list will not exceed 1000 words.
- Each word in the list will have a length between 1 and 20 characters.
Optimal Approach & Strategy
The optimal approach involves using dynamic programming and a hashmap to store the longest chain of words that end with each letter. This approach allows us to efficiently find the longest chain in O(n^2) time complexity.
Brute Force Approach
A naive approach would involve generating all possible permutations of the input list and checking each permutation to see if it forms a valid chain. This approach would have a time complexity of O(n!), making it impractical for large inputs.
Asked in Top Tech Interviews
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.