Shared Dance Moves

Mediumdynamic programmingAlso known as Longest Common Subsequence

Two dance groups are performing a joint finale. Each group has its own routine, written down as one letter per move: S for a spin, J for a jump, P for a pose, and so on. For the last minute, both groups want to dance together, so the finale uses moves that appear in both routines, in the same order.

Each group may leave out moves from its own routine, but it may not reorder them. How long can the shared finale be?

Your task

Write sharedMoves(first, second). Return the length of the longest sequence of letters that can be made from first by deleting some letters, and also from second by deleting some letters. The kept letters stay in their original order but do not need to be next to each other.

If either routine is empty, or they share no move at all, return 0.

sharedMoves(first: string, second: string) → int

Examples

Example 1

Input

first = "SPJTS"
second = "PSJST"

Output

Why

P, J, T appears in order in both: in SPJTS at positions 1, 2, 3, and in PSJST at positions 0, 2, 4. S, J, S also works. No 4 moves appear in the same order in both.

Example 2

Input

first = "SJ"
second = "JS"

Output

Why

Both routines have a spin and a jump, but in opposite orders. You can keep only one of them, so the answer is 1, not 2.

Constraints

0 ≤ first.length, second.length ≤ 1,000
Both strings contain only uppercase letters A to Z.

Start with brute force

List every way to delete letters from the first routine (2ⁿ choices), and check whether each result can also be made from the second. With 1,000 moves that is 2¹⁰⁰⁰ candidates.

Counting the letters the two routines have in common is fast but ignores order: it says 2 for SJ and JS. Looking only for a shared run of back-to-back moves is also wrong: it misses moves that are spread out.

Hints

0 of 4 shown

Hint 1
Compare the last moves of the two routines. If they are the same move, should the finale end with it? If they differ, at least one of them cannot be the finale's last move. Which?
Hint 2
If the last letters match, use them: the answer is 1 + the answer for both routines without their last letter. If they differ, drop the last letter of one routine or the other, and take the better of the two results.
Hint 3
So the answer only depends on two prefix lengths. Let best[i][j] be the answer for the first i moves of first and the first j moves of second. A row or column of zeros covers the empty prefixes.
Hint 4
Fill the table row by row: if first[i - 1] === second[j - 1], then best[i][j] = best[i - 1][j - 1] + 1, otherwise max(best[i - 1][j], best[i][j - 1]). The answer is in the bottom-right cell.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

Look at the two last moves. If they are equal, the finale can end with that move, and the rest is the answer for both prefixes one shorter. If they are different, one of them is not in the finale, so drop it from its routine. You do not know which, so try both and keep the bigger.

That gives a table indexed by prefix lengths. Trace the first example, SPJTS (rows) against PSJST (columns), with row 0 and column 0 as the empty prefixes:

	P	S	J	S	T
(empty)	0	0	0	0	0
S	0	1	1	1	1
P	1	1	1	1	1
J	1	1	2	2	2
T	1	1	2	2	3
S	1	2	2	3	3

Row S, first column S: a match, so the diagonal 0 + 1 = 1.
Row P, column P: a match, 0 + 1 = 1. Next to it, P ≠ S, so max(above 1, left 1) = 1.
Row J, column J: a match, so the diagonal (row P, first column S) 1 + 1 = 2.
Row T, column T: a match, so the diagonal (row J, second column S) 2 + 1 = 3.
Last row S, column T: S ≠ T, so max(above 3, left 3) = 3. Answer 3.

For SJ against JS the same rules give 1: each letter matches once, but the two matches sit on different diagonals, so neither can build on the other.

Each cell only reads the row above and the cell to its left, so the code keeps just two rows.

Reference solution

function sharedMoves(first, second) {
  const m = second.length;
  // prev[j] = answer for the previous prefix of first and second[0..j)
  let prev = new Array(m + 1).fill(0);
  for (let i = 1; i <= first.length; i++) {
    const cur = new Array(m + 1).fill(0);
    for (let j = 1; j <= m; j++) {
      if (first[i - 1] === second[j - 1]) cur[j] = prev[j - 1] + 1; // use the shared move
      else cur[j] = Math.max(prev[j], cur[j - 1]);               // drop one last move
    }
    prev = cur;
  }
  return prev[m];
}

def shared_moves(first, second):
    m = len(second)
    # prev[j] = answer for the previous prefix of first and second[:j]
    prev = [0] * (m + 1)
    for a in first:
        cur = [0] * (m + 1)
        for j in range(1, m + 1):
            if a == second[j - 1]:
                cur[j] = prev[j - 1] + 1  # use the shared move
            else:
                cur[j] = max(prev[j], cur[j - 1])  # drop one last move
        prev = cur
    return prev[m]

TimeO(n × m)One constant-time cell per pair of prefix lengths.

SpaceO(m)Two rows of the table at a time.

Learn the idea: DP on Strings Strings

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code