40. Longest Common Audio-Feature Subsequence

Problem

Two audio segments — a reference template and a live streamed clip — have each been quantized into a sequence of integer feature codes. Because the live clip runs at a slightly different pace and has extra frames mixed in (noise, silence, mic jitter), a frame-for-frame comparison is too strict.

Instead, measure the length of the longest common subsequence (not necessarily contiguous) of feature codes shared between the two sequences — a standard alignment-tolerant similarity score.

Source: src/40_longest_common_audio_subsequence.py

def longest_common_feature_subsequence(reference: list[int], live: list[int]) -> int:
    ...

Examples:
>>> longest_common_feature_subsequence([3, 1, 4, 1, 5, 9], [1, 4, 1, 9, 2])
4

>>> longest_common_feature_subsequence([1, 2, 3], [4, 5, 6])
0

Step-by-Step Approach

1. Recognize this as textbook Longest Common Subsequence over two integer sequences instead of two strings — the algorithm doesn't care that the elements are quantized audio-feature codes rather than characters.
2. Define dp[i][j] as the LCS length of reference[:i] and live[:j], with dp[0][*] = dp[*][0] = 0 as the base case.
3. When reference[i-1] == live[j-1], the codes match: extend the best subsequence found strictly before both positions, so dp[i][j] = dp[i-1][j-1] + 1.
4. When they don't match, the best is whichever of “drop this reference frame” or “drop this live frame” scored higher: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
5. Fill the table row by row; since each row only depends on the row above and the current row so far, keep just two rolling rows instead of the full O(m · n) table to cut space to O(n).
6. The answer is the final cell, dp[m][n] — the LCS length of the full sequences.

The key insight is the same one behind every LCS variant: a match at (i, j) can only ever extend a subsequence built from strictly earlier positions in both sequences, which is exactly what makes the diagonal-plus-one recurrence correct and why it generalizes cleanly from strings to any comparable element type.

Reference solution

def longest_common_feature_subsequence(reference: list[int], live: list[int]) -> int:
    # classic LCS DP: dp[i][j] = LCS length of reference[:i] and live[:j]
    # O(m * n) time, O(n) space via rolling rows
    m, n = len(reference), len(live)
    prev = [0] * (n + 1)
    for i in range(1, m + 1):
        curr = [0] * (n + 1)
        for j in range(1, n + 1):
            if reference[i - 1] == live[j - 1]:
                # codes match: extend the best subsequence found before both positions
                curr[j] = prev[j - 1] + 1
            else:
                # skip one side or the other, whichever kept the longer match so far
                curr[j] = max(prev[j], curr[j - 1])
        prev = curr
    return prev[n]


TEST_CASES = [
    {"input": {"reference": [3, 1, 4, 1, 5, 9], "live": [1, 4, 1, 9, 2]}, "expected": 4},
    {"input": {"reference": [1, 2, 3], "live": [4, 5, 6]}, "expected": 0},
    {"input": {"reference": [1, 2, 3], "live": [1, 2, 3]}, "expected": 3},
    {"input": {"reference": [], "live": [1, 2, 3]}, "expected": 0},
    {"input": {"reference": [5, 1, 2, 3, 9], "live": [1, 3]}, "expected": 2},
]


def main():
    for i, case in enumerate(TEST_CASES):
        reference = case["input"]["reference"]
        live = case["input"]["live"]
        expected = case["expected"]
        print(f"Test {i}: longest_common_feature_subsequence(reference={reference}, live={live})")
        m, n = len(reference), len(live)
        prev = [0] * (n + 1)
        for row_i in range(1, m + 1):
            curr = [0] * (n + 1)
            for col_j in range(1, n + 1):
                if reference[row_i - 1] == live[col_j - 1]:
                    curr[col_j] = prev[col_j - 1] + 1
                else:
                    curr[col_j] = max(prev[col_j], curr[col_j - 1])
            print(f"  after reference[{row_i - 1}]={reference[row_i - 1]}: dp row = {curr}")
            prev = curr
        result = longest_common_feature_subsequence(reference=reference, live=live)
        assert result == expected
        print(f"PASSED: {result}")
    print(f"All {len(TEST_CASES)} test cases passed.")


if __name__ == "__main__":
    main()

Key Functions & Tricks

• prev, curr: list[int] — rolling DP rows, cutting space from O(m · n) to O(n)
• reference[i - 1] == live[j - 1] — the match test that drives the diagonal-plus-one case
• curr[j] = prev[j - 1] + 1 — extend on a match, using the diagonal (both-advanced) predecessor
• curr[j] = max(prev[j], curr[j - 1]) — skip one side on a mismatch, keeping whichever skip scored higher

How to Recognize This Pattern