Dynamic Programming

LCS Table — dp[i][j] = LCS length of s1[0..i-1] and s2[0..j-1]

↓s1 / s2→

ε

S

A

T

U

R

D

A

Y

ε

S

U

N

D

A

Y

Press Play to fill the DP table character by character.

LCS Table

Press Play to fill the 2D DP table and discover the longest common subsequence.

Debugger · v1.0

LIVE

1function lcs(s1, s2) {

2 const m = s1.length, n = s2.length;

3 // 1: Build (m+1) x (n+1) table

4 const dp = Array(m+1).fill(0)

5 .map(() => Array(n+1).fill(0));

7 // 3: Fill row by row

8 for (let i = 1; i <= m; i++) {

9 for (let j = 1; j <= n; j++) {

10 if (s1[i-1] === s2[j-1]) {

11 // 5: Characters match → diagonal + 1

12 dp[i][j] = dp[i-1][j-1] + 1;

13 } else {

14 // 8: No match → take the max

15 dp[i][j] = Math.max(

16 dp[i-1][j], // skip s1[i-1]

17 dp[i][j-1] // skip s2[j-1]

18 );

19 }

20 }

21 }

23 // 11: Backtrack to build LCS string

24 let i = m, j = n, result = '';

25 while (i > 0 && j > 0) {

26 if (s1[i-1] === s2[j-1]) {

27 // 12: Match — prepend char, go diagonal

28 result = s1[i-1] + result; i--; j--;

29 } else if (dp[i-1][j] >= dp[i][j-1]) {

30 // 14: Go up

31 i--;

32 } else {

33 // 16: Go left

34 j--;

35 }

36 }

37 // 18: Return LCS string

38 return result;

39}

Debugger · v1.0

LIVE

1function lcs(s1, s2) {

2 const m = s1.length, n = s2.length;

3 // 1: Build (m+1) x (n+1) table

4 const dp = Array(m+1).fill(0)

5 .map(() => Array(n+1).fill(0));

7 // 3: Fill row by row

8 for (let i = 1; i <= m; i++) {

9 for (let j = 1; j <= n; j++) {

10 if (s1[i-1] === s2[j-1]) {

11 // 5: Characters match → diagonal + 1

12 dp[i][j] = dp[i-1][j-1] + 1;

13 } else {

14 // 8: No match → take the max

15 dp[i][j] = Math.max(

16 dp[i-1][j], // skip s1[i-1]

17 dp[i][j-1] // skip s2[j-1]

18 );

19 }

20 }

21 }

23 // 11: Backtrack to build LCS string

24 let i = m, j = n, result = '';

25 while (i > 0 && j > 0) {

26 if (s1[i-1] === s2[j-1]) {

27 // 12: Match — prepend char, go diagonal

28 result = s1[i-1] + result; i--; j--;

29 } else if (dp[i-1][j] >= dp[i][j-1]) {

30 // 14: Go up

31 i--;

32 } else {

33 // 16: Go left

34 j--;

35 }

36 }

37 // 18: Return LCS string

38 return result;

39}

State Inspector

No variables in scope.

Preset:

Longest Common Subsequence (LCS)

Step 1 of 6

Find the longest sequence of characters that appears in both strings in the same relative order (not necessarily contiguous). A fundamental DP problem used in diff tools, bioinformatics, and version control.

The Problem

Given two strings s1 and s2, find the longest subsequence present in both. A subsequence keeps the original order but can skip characters. For example: s1 = "SUNDAY", s2 = "SATURDAY" → LCS = "SDAY" (length 4).

S

U

N

D

A

Y

S

A

T

U

R

D

A

Y

Green = shared subsequence "SDAY"