Introduction

The general longest common subsequence problem is usually solved in O(nm) time with dynamic programming. An O(n log n) solution is possible only for special cases, most commonly when one sequence can be mapped to unique positions in the other and the problem reduces to finding a longest increasing subsequence.

The Key Restriction

For arbitrary strings or arrays with repeated values, you should not expect a clean O(n log n) algorithm for exact LCS in normal practice. The faster approach works when each value in one sequence maps unambiguously to a single position in the other, such as when the sequences are permutations or contain unique comparable elements.

Once that condition holds, LCS becomes an LIS problem:

1. map each item in the first sequence to its index
2. rewrite the second sequence as those indices
3. find the longest increasing subsequence of the mapped indices

If the order is increasing in the index array, the corresponding values appear in the same order in both original sequences.

From LCS to LIS

Suppose:

• first sequence: [3, 1, 4, 2, 5]
• second sequence: [1, 2, 3, 4, 5]

Map the first sequence to positions:

• '3 -> 0'
• '1 -> 1'
• '4 -> 2'
• '2 -> 3'
• '5 -> 4'

Now rewrite the second sequence using those positions:

• '[1, 3, 0, 2, 4]'

The LIS of that array has length 3, which matches the LCS length.

Python Implementation

The following function returns the LCS length for the unique-element case:

1from bisect import bisect_left
2
3
4def lcs_length_unique(a, b):
5    positions = {value: index for index, value in enumerate(a)}
6    mapped = [positions[value] for value in b if value in positions]
7
8    tails = []
9    for value in mapped:
10        i = bisect_left(tails, value)
11        if i == len(tails):
12            tails.append(value)
13        else:
14            tails[i] = value
15
16    return len(tails)
17
18
19first = [3, 1, 4, 2, 5]
20second = [1, 2, 3, 4, 5]
21
22print(lcs_length_unique(first, second))

Output:

3

The tails array stores the smallest possible tail value for an increasing subsequence of each length. That is the standard O(n log n) LIS technique.

Recovering the Subsequence

If you want the subsequence itself rather than just the length, you need to keep predecessor links and track where each tail came from.

1from bisect import bisect_left
2
3
4def lcs_unique(a, b):
5    positions = {value: index for index, value in enumerate(a)}
6    items = [(positions[value], value) for value in b if value in positions]
7
8    tails = []
9    tails_idx = []
10    prev = [-1] * len(items)
11
12    for i, (pos, _) in enumerate(items):
13        j = bisect_left(tails, pos)
14        if j == len(tails):
15            tails.append(pos)
16            tails_idx.append(i)
17        else:
18            tails[j] = pos
19            tails_idx[j] = i
20
21        if j > 0:
22            prev[i] = tails_idx[j - 1]
23
24    result = []
25    k = tails_idx[-1]
26    while k != -1:
27        result.append(items[k][1])
28        k = prev[k]
29
30    return list(reversed(result))
31
32
33print(lcs_unique([3, 1, 4, 2, 5], [1, 2, 3, 4, 5]))

Output:

[1, 4, 5]

That result is a valid LCS for this constrained input type.

When This Approach Is Appropriate

Use the O(n log n) method when the sequences behave like unique rankings, IDs, or permutations. It is common in ordering problems where duplicated symbols are not central to the task.

If duplicates matter, the simple mapping breaks down because one value can correspond to multiple valid positions. Then the classic dynamic programming formulation is still the safer default.

Common Pitfalls

• Claiming O(n log n) for general LCS. The reduction works only under specific constraints.
• Ignoring duplicates. A single dictionary map is not enough when values repeat.
• Confusing subsequence with substring. LCS does not require contiguous matches.
• Returning only LIS length without confirming the index mapping truly represents the original LCS problem.
• Using this optimization when sequence sizes are small enough that plain dynamic programming is simpler and clearer.

Summary

• Exact LCS for arbitrary sequences is usually approached with O(nm) dynamic programming.
• 'O(n log n) becomes possible when the problem can be reduced to LIS through unique position mapping.'
• The workflow is map positions, transform the second sequence, then compute LIS.
• This method is excellent for permutations or unique-element order comparisons.
• If duplicates or general inputs matter, stick with the standard dynamic programming solution.