Longest Chained Subsequence — Problem Statement & Solution Guide
Problem Description
Given a list of strings codes, determine the length of the longest subsequence where each string starts with the last character of the previous string.
Examples
Input
['abc', 'cde', 'efg', 'fgh']
Output
3
Explanation: Step-by-step: 1. Start with 'abc'. 2. The last character of 'abc' is 'c', which is the first character of 'cde'. 3. The last character of 'cde' is 'e', which is the first character of 'efg'. 4. The last character of 'efg' is 'g', which is the first character of 'fgh'. 5. The longest subsequence is 'abc', 'cde', 'efg', 'fgh'. 6. The length of the longest subsequence is 4, but since 'fgh' does not start with the last character of 'efg', the correct answer is 3.
Input
['a', 'b', 'c']
Output
2
Explanation: Step-by-step: 1. Start with 'a'. 2. The last character of 'a' is 'a', which is the first character of 'b'. 3. The last character of 'b' is 'b', which is the first character of 'c'. 4. The longest subsequence is 'a', 'b', 'c'. 5. The length of the longest subsequence is 3, but since 'b' does not start with the last character of 'a', the correct answer is 2.
Constraints
- 2 <= number of transmission codes <= 100
- 1 <= length of each transmission code <= 10
Optimal Approach & Strategy
The optimal approach uses dynamic programming to build a graph where each code is a node, and edges connect codes where one code ends with the character another starts, allowing for a much more efficient exploration of possible sequences.
Brute Force Approach
A naive approach could involve checking every possible sequence of codes, resulting in a time complexity of O(n!). This approach quickly becomes impractical as the number of codes increases.
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.