Longest Prefix Chain Length — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Strings and solve the Longest Prefix Chain Length problem optimally.
O(N·Lavg + |target|)O(N·Lavg)Problem Description
Given an integer n, an array messages of n strings, and a string target, compute the greatest integer k for which there exists a sequence s1,s2,…,sk satisfying: (1) sk equals target; (2) for every i from 1 to k‑1, si is a proper prefix of si+1 (i.e., si ≠ si+1 and si matches the first |si| characters of si+1); (3) each si appears at least once in messages (the same message may be reused any number of times). Return k. If target does not occur in messages, return 0.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Longest Prefix Chain Length"
WHY DOES IT MATTER?
Understanding prefix chains teaches candidates how to exploit inherent ordering in strings, turning a combinatorial explosion into a linear scan, a skill useful for autocomplete, dictionary compression, and hierarchical naming schemes.
OPTIMIZATION CHALLENGE
The key insight is that the prefix relation imposes a total order by length, so the longest chain is just the count of present prefixes – eliminating the need for DP or graph traversal.
REAL-WORLD CONNECTION
Think of versioned APIs where each newer version extends the previous one; determining the longest supported upgrade path is analogous to finding the deepest prefix chain that exists in the deployment logs.
In an interview, immediately ask whether the target itself must be present; this quick validation often lets you return 0 early and demonstrates disciplined problem scoping.
COMPLEXITY AT A GLANCE
O(N·Lavg + |target|)O(N·Lavg)Core Theory — Why This Approach?
The problem reduces to finding the longest chain of strings where each is a proper prefix of the next and the final string equals the target. Because the prefix relation is transitive and strictly ordered by length, any valid chain must consist of a subset of the target’s prefixes sorted by increasing length. Therefore the optimal solution is simply to count how many of those prefixes (including the target itself) appear in the given message list. A naïve approach would try to enumerate all possible sequences or perform recursive prefix checks, leading to exponential blow‑up for large n, whereas using a hash set to test membership of each target prefix yields linear time relative to the total input size.
Interview Questions on This Problem
Q1How would you compute the longest prefix chain if the messages list is extremely large (e.g., 10⁶ strings) and the target length is up to 10⁵?
Store all messages in an unordered_set (or a trie if memory‑tight) for O(1) average look‑ups, then iterate over the target’s prefixes from length 1 to |target|, counting those present; the answer is the count plus one for the target itself, provided the target is in the set.
Q2Can the solution be adapted to handle the case where each message can be used only once in the chain?
Yes – you would need to treat the problem as a longest path in a DAG where each node (prefix) has a capacity of one; however, because prefixes are uniquely identified by length, the greedy count still works as long as duplicates are ignored, otherwise you’d need a bipartite matching or DP with usage flags, increasing complexity to O(L + n).
Q3Why is a trie sometimes preferred over a hash set for prefix‑related problems, and would it help here?
A trie enables prefix‑range queries and can quickly enumerate all existing prefixes of the target in O(L) without constructing each prefix string; however, for this specific problem we only need existence checks, so a hash set is simpler and equally efficient in expected time.
Examples
Input
5 [a,ab,abc,abcd,abcde] abcd
Output
4
Explanation: All four strings a → ab → abc → abcd are present in messages, each is a proper prefix of the next, and the last equals target, giving a chain length of 4.
Input
6 [x,xy,xyz,xy,xyz,xyzz] xyzz
Output
4
Explanation: A valid chain is x → xy → xyz → xyzz. All elements exist in messages (some are reused), each is a proper prefix of the following one, and the final element matches target, so the maximum length is 4.
Input
4 [hello,world,hi,hey] test
Output
0
Explanation: The target string "test" never appears in messages, therefore no chain can end with it and the answer is 0.
Constraints
- 1 <= n <= 200000
- Each string in messages and target consists only of lowercase English letters
- 1 <= length of any string <= 100
- The total sum of lengths of all strings in messages does not exceed 2·10^6
Optimal Approach & Strategy
Insert all messages into a hash set, then scan the target’s prefixes from shortest to longest, counting those present; answer is count + 1 if the target exists, otherwise 0.
Brute Force Approach
Generate every possible ordering of messages, test each sequence for the prefix property, and keep the longest that ends with the target – exponential time.
Code Solutions
function longestPrefixChain(messages, target){
const set = new Set(messages);
if(!set.has(target)) return 0;
let cnt = 1; // target itself
for(let len=1; len<target.length; ++len){
if(set.has(target.slice(0,len))) cnt++;
}
return cnt;
}
function main(){
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/);
let idx=0;
const n = parseInt(data[idx++]);
const msgs = [];
for(let i=0;i<n;i++) msgs.push(data[idx++]);
const target = data[idx++]||'';
console.log(longestPrefixChain(msgs,target).toString());
}
main();#include <bits/stdc++.h>
using namespace std;
int longestPrefixChain(int n, const vector<string>& messages, const string& target){
unordered_set<string> S(messages.begin(), messages.end());
if(S.find(target)==S.end()) return 0;
int cnt=1; // target itself
for(size_t len=1; len<target.size(); ++len){
if(S.find(target.substr(0,len))!=S.end()) ++cnt;
}
return cnt;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; if(!(cin>>n)) return 0;
vector<string> msgs(n);
for(int i=0;i<n;++i) cin>>msgs[i];
string target; cin>>target;
cout<<longestPrefixChain(n,msgs,target);
return 0;
}
import java.io.*;
import java.util.*;
public class Main {
static int longestPrefixChain(List<String> messages, String target){
Set<String> set = new HashSet<>(messages);
if(!set.contains(target)) return 0;
int cnt = 1; // target itself
for(int len=1; len<target.length(); ++len){
if(set.contains(target.substring(0,len))) cnt++;
}
return cnt;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line;
line = br.readLine();
if(line==null) return;
int n = Integer.parseInt(line.trim());
List<String> msgs = new ArrayList<>();
int read = 0;
while(read < n){
StringTokenizer st = new StringTokenizer(br.readLine());
while(st.hasMoreTokens() && read < n){
msgs.add(st.nextToken());
read++;
}
}
String target = br.readLine();
System.out.println(longestPrefixChain(msgs, target));
}
}
def longest_prefix_chain(messages, target):
s = set(messages)
if target not in s:
return 0
cnt = 1 # target itself
for l in range(1, len(target)):
if target[:l] in s:
cnt += 1
return cnt
if __name__ == "__main__":
import sys
data = sys.stdin.read().strip().split()
if not data:
sys.exit(0)
it = iter(data)
n = int(next(it))
msgs = [next(it) for _ in range(n)]
target = next(it, "")
print(longest_prefix_chain(msgs, target))
function longestPrefixChain(messages, target){
const set = new Set(messages);
if(!set.has(target)) return 0;
let cnt = 1; // target itself
for(let len=1; len<target.length; ++len){
if(set.has(target.slice(0,len))) cnt++;
}
return cnt;
}
function main(){
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/);
let idx=0;
const n = parseInt(data[idx++]);
const msgs = [];
for(let i=0;i<n;i++) msgs.push(data[idx++]);
const target = data[idx++]||'';
console.log(longestPrefixChain(msgs,target).toString());
}
main();
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.