BackmediumStringsPaytm

Longest Prefix Chain Length Solution

Problem Statement

Given a list of strings messages and a target string target, determine the length of the longest chain of strings where each string is a prefix of the next and the last string is target.

Example 1
Input
messages = ['a', 'ab', 'abc'], target = 'abc'
Output
3

Explanation: Step-by-step: 1. Start with the target string 'abc'. 2. Find the longest prefix of 'abc' in the messages list, which is 'abc' itself. 3. The length of the chain is 1. 4. Now, find the longest prefix of 'abc' in the messages list that is not 'abc', which is 'ab'. 5. The length of the chain is 2. 6. Now, find the longest prefix of 'ab' in the messages list, which is 'a'. 7. The length of the chain is 3. 8. Since we cannot find a longer chain, the final answer is 3.

Example 2
Input
messages = ['a', 'ab'], target = 'ab'
Output
2

Explanation: Step-by-step: 1. Start with the target string 'ab'. 2. Find the longest prefix of 'ab' in the messages list, which is 'ab' itself. 3. The length of the chain is 1. 4. Now, find the longest prefix of 'ab' in the messages list that is not 'ab', which is 'a'. 5. The length of the chain is 2. 6. Since we cannot find a longer chain, the final answer is 2.

Constraints

  • 2 <= number of messages <= 100
  • 1 <= length of each message <= 10
  • All messages are lowercase English letters.

More Strings

Rearrangement Equivalence CheckereasyAnagram VerifiereasyCharacter Frequency CountereasyFascinating Frequency StringeasyString Character MatchereasyString Reversal CheckeasyMatching ExtremeseasySymmetry Score of a Stringeasy
View all problems →
Live Compiler1 Free Run Available
Loading Editor...
Test Cases & Output
Click "Run" to test your 1 free compile trial!

🚀 Practice this problem

Run code, get AI hints & track streak

Sign Up Free

Longest Prefix Chain Length — Problem Statement & Solution Guide

StringsMediumMixed
TimeO(n)
|
SpaceO(n)

Problem Description

Given a list of strings messages and a target string target, determine the length of the longest chain of strings where each string is a prefix of the next and the last string is target.

Examples

Example 1

Input

messages = ['a', 'ab', 'abc'], target = 'abc'

Output

3

Explanation: Step-by-step: 1. Start with the target string 'abc'. 2. Find the longest prefix of 'abc' in the messages list, which is 'abc' itself. 3. The length of the chain is 1. 4. Now, find the longest prefix of 'abc' in the messages list that is not 'abc', which is 'ab'. 5. The length of the chain is 2. 6. Now, find the longest prefix of 'ab' in the messages list, which is 'a'. 7. The length of the chain is 3. 8. Since we cannot find a longer chain, the final answer is 3.

Example 2

Input

messages = ['a', 'ab'], target = 'ab'

Output

2

Explanation: Step-by-step: 1. Start with the target string 'ab'. 2. Find the longest prefix of 'ab' in the messages list, which is 'ab' itself. 3. The length of the chain is 1. 4. Now, find the longest prefix of 'ab' in the messages list that is not 'ab', which is 'a'. 5. The length of the chain is 2. 6. Since we cannot find a longer chain, the final answer is 2.

Constraints

  • 2 <= number of messages <= 100
  • 1 <= length of each message <= 10
  • All messages are lowercase English letters.

Optimal Approach & Strategy

The optimized approach uses dynamic programming to store the length of the longest chain ending at each message, and then updates it based on whether a shorter message is a prefix of the current message, resulting in a time complexity of O(n^2).

Brute Force Approach

The brute-force approach involves checking all possible combinations of messages to find the longest chain, resulting in a time complexity of O(2^n). This approach is inefficient and impractical for large inputs.

Asked in Top Tech Interviews

Paytm

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.

Sign Up & Solve Free →Browse All Problems