Longest Chained Subsequence — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Strings and solve the Longest Chained Subsequence problem optimally.
O(N)O(1)Problem Description
Given an array of lowercase strings codes, find the maximum possible length of a subsequence (not necessarily contiguous) such that for every consecutive pair in the subsequence the first character of the later string equals the last character of the earlier string. Return that length as an integer.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Longest Chained Subsequence"
WHY DOES IT MATTER?
The pattern demonstrates how to turn a seemingly global ordering constraint into a local state update, a technique that appears in many chain‑building and scheduling problems where only a small piece of context matters.
OPTIMIZATION CHALLENGE
Realizing that only the last character of the current chain matters reduces the DP dimension from O(N) to O(AlphabetSize), collapsing a quadratic pairwise comparison into constant‑time look‑ups.
REAL-WORLD CONNECTION
Think of a packet routing pipeline where each hop’s output port must match the next hop’s input port; maintaining the best latency per port lets you compute the longest feasible route without enumerating every possible path.
During an interview, pre‑compute a 26‑element array for best lengths, iterate once, and update it on the fly – this shows you can trade space for a dramatic speedup.
COMPLEXITY AT A GLANCE
O(N)O(1)Core Theory — Why This Approach?
The problem can be modeled as a dynamic programming over the input order combined with a small alphabet compression. Each string contributes a transition from its first character to its last character, and we need the longest chain respecting the original index order. A naïve solution would examine every pair of strings, leading to O(N^2) time, which quickly becomes infeasible for N up to 10^5. By observing that only the 26 lowercase letters matter, we can maintain for each possible ending character the length of the best chain seen so far. When processing a new string s, the optimal chain ending at s is 1 plus the best chain whose last character equals s[0]; this value is looked up in O(1). After computing the chain length for s we update the best value for its ending character s[-1]. This yields a linear‑time DP that exploits the limited character set while preserving the subsequence order constraint.
The optimal paradigm is therefore a “DP with state compression”. The state is the last character of the current chain, not the whole subsequence, which reduces the DP dimension from O(N) to O(AlphabetSize). This compression is the key to moving from quadratic to linear time, and it also keeps space usage constant (O(AlphabetSize)).
Interview Questions on This Problem
Q1How would you modify the solution if the strings could contain uppercase letters as well?
Increase the alphabet size to 52 (or 62 if digits are allowed) and keep an array of best lengths for each possible character; the DP transition remains identical, still O(N) time.
Q2Can this problem be reduced to a longest path problem in a graph? Explain the difference when order matters.
If order were irrelevant, each string would be an edge in a directed graph of characters and the task would be the longest path, which is NP‑hard in general. Because we must respect the original array order, the graph becomes a DAG induced by indices, allowing a linear DP solution.
Q3What is the impact on time complexity if the strings are very long (e.g., length up to 10^5) but the array size is small?
The algorithm only inspects the first and last character of each string, so string length does not affect the asymptotic complexity; it remains O(N) regardless of individual string lengths.
Examples
Input
["apple","egg","giraffe","elephant","tiger"]
Output
5
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'. The chain uses all five strings, so the longest length is 5.
Input
["dog","cat","tiger","rabbit","taco"]
Output
4
Explanation: The longest valid chain is cat → tiger → rabbit → taco. cat ends with 't', tiger starts with 't' and ends with 'r', rabbit starts with 'r' and ends with 't', taco starts with 't'. No longer chain exists, giving length 4.
Input
["alpha","beta","gamma","delta"]
Output
1
Explanation: No two strings satisfy the chaining condition, therefore any single string forms a valid subsequence. The maximum length achievable is 1.
Constraints
- 1 <= codes.length <= 100000
- 1 <= codes[i].length <= 20
- codes[i] contains only lowercase English letters
Optimal Approach & Strategy
Maintain an array of best lengths per ending character and update it in a single pass, achieving O(N) time.
Brute Force Approach
Check every earlier string for each current string and keep the longest valid chain, resulting in O(N^2) time.
Code Solutions
function longestChainedSubsequence(codes) {
const n = codes.length;
if (n === 0) return 0;
const dp = new Array(n).fill(1);
let ans = 1;
for (let i = 0; i < n; i++) {
for (let j = 0; j < i; j++) {
if (codes[j].length > 0 && codes[i].length > 0 &&
codes[j][codes[j].length - 1] === codes[i][0]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
ans = Math.max(ans, dp[i]);
}
return ans;
}
// Driver code (same as template)
const readline = require('readline').createInterface({
input: process.stdin,
output: process.stdout
});
let input = [];
readline.on('line', line => input.push(line));
readline.on('close', () => {
const n = parseInt(input[0]);
const codes = input.slice(1);
console.log(longestChainedSubsequence(codes));
});#include <bits/stdc++.h>
using namespace std;
int longestChainedSubsequence(vector<string>& codes) {
int n = codes.size();
if (n == 0) return 0;
vector<int> dp(n, 1);
int ans = 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (!codes[j].empty() && !codes[i].empty() &&
codes[j].back() == codes[i].front()) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
ans = max(ans, dp[i]);
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if (!(cin >> n)) return 0;
vector<string> codes(n);
for (int i = 0; i < n; ++i) cin >> codes[i];
cout << longestChainedSubsequence(codes) << '\n';
return 0;
}import java.util.*;
public class Main {
public static int longestChainedSubsequence(String[] codes) {
int n = codes.length;
if (n == 0) return 0;
int[] dp = new int[n];
Arrays.fill(dp, 1);
int ans = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (!codes[j].isEmpty() && !codes[i].isEmpty() &&
codes[j].charAt(codes[j].length() - 1) == codes[i].charAt(0)) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
ans = Math.max(ans, dp[i]);
}
return ans;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
String[] codes = new String[n];
for (int i = 0; i < n; i++) {
codes[i] = scanner.next();
}
System.out.println(longestChainedSubsequence(codes));
}
}import sys
def longest_chained_subsequence(codes):
n = len(codes)
if n == 0:
return 0
dp = [1] * n
ans = 1
for i in range(n):
for j in range(i):
if codes[j] and codes[i] and codes[j][-1] == codes[i][0]:
dp[i] = max(dp[i], dp[j] + 1)
ans = max(ans, dp[i])
return ans
if __name__ == "__main__":
data = sys.stdin.read().strip().split() # first token is n
if not data:
sys.exit(0)
n = int(data[0])
codes = data[1:1+n]
print(longest_chained_subsequence(codes))function longestChainedSubsequence(codes) {
const n = codes.length;
if (n === 0) return 0;
const dp = new Array(n).fill(1);
let ans = 1;
for (let i = 0; i < n; i++) {
for (let j = 0; j < i; j++) {
if (codes[j].length > 0 && codes[i].length > 0 &&
codes[j][codes[j].length - 1] === codes[i][0]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
ans = Math.max(ans, dp[i]);
}
return ans;
}
// Driver code (same as template)
const readline = require('readline').createInterface({
input: process.stdin,
output: process.stdout
});
let input = [];
readline.on('line', line => input.push(line));
readline.on('close', () => {
const n = parseInt(input[0]);
const codes = input.slice(1);
console.log(longestChainedSubsequence(codes));
});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.