Longest shared pattern between two signal streams

Question

Two models each output a sequence of daily calls, like "up" / "dn" / "flat". You want the length of the longest common subsequence: the longest ordered pattern that appears in both (keeping order, but the matching days need not be consecutive in either stream).

a = ["up", "dn", "up", "dn", "up"]
b = ["dn", "up", "up", "dn"]
-> 3        # e.g. "dn", "up", "dn"

Return the length of the longest common subsequence in O(m*n) time.

Accepted Answer

Let dp[i][j] be the LCS length of the first i calls of a and first j of b. If the current calls match, the answer grows by one on top of the smaller prefixes: dp[i][j] = dp[i-1][j-1] + 1. If they differ, drop one element from whichever side helps more: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). A border row and column of zeros handle the empty-prefix base case. For the example the table fills to dp[5][4] = 3. Time O(mn), space O(mn), reducible to O(min(m, n)) by keeping only two rows. Edge cases: either stream empty gives 0; note this is a subsequence (gaps allowed), unlike the longest common su…

Longest shared pattern between two signal streams

Your answer

More Coding questions