Standard Bar Dynamic Programming · DP on Strings O(n*m) · O(n*m)
A hardware team tracks two firmware branches and must print the exact sequence of module tokens both branches inherited from their common ancestor — not just how many. The lineage tool rebuilds the shared token string by walking the completion table backwards, emitting each token where the branches agree.
Input: Integers n and m, plus strings s1 and s2 of lengths n and m.
Output: Return one longest common subsequence as a string. If several exist, any valid one is accepted.
1 <= n, m <= 1000strings consist of uppercase or lowercase English lettersInput: {"n":5,"m":3,"s1":"abcde","s2":"ace"}
Output: "ace"
"ace" appears in order within both strings and no longer anchor exists.
Input: {"n":3,"m":4,"s1":"abc","s2":"bacd"}
Output: "bc"
"ac" also has length 2, so "bc" is an equally valid reconstruction.