String DP — longest common substring, LCS of three strings, space-optimised LCS, interleaving, boolean parenthesization

Medium

Problem

Two-string (and three-string) DPs:

Longest common substring — must be contiguous in both strings. LCS of three strings. LCS in O(min(m, n)) space. Interleaving String — can s3 be formed by interleaving s1 and s2 while keeping each string's order? Boolean parenthesization — count the ways to parenthesise a T/F expression with & | ^ so that it evaluates to true.

Example 1

Input:  interleave s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Example 2

Input:  longest common substring "ABCDGH", "ACDGHR"
Output: 4 ("CDGH")

Also asked as: Longest Common Substring · LCS (Longest Common Subsequence) of three strings · Space Optimized Solution of LCS · Find if a string is interleaved of two other strings · Boolean Parenthesization Problem

Test cases

Case 1

Input:    "ABCDGH", "ACDGHR"
Expected: 4

Case 2

Input:    "abc", "xyz"
Expected: 0

Case 3

Input:    "abc", "abc"
Expected: 3

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution2 approaches

1. Longest common SUBSTRING (contiguous)

Time O(n·m)Space O(m) with a rolling row

dp[i][j] = length of the common suffix of a[..i] and b[..j] = dp[i−1][j−1] + 1 when chars match, else 0. Answer is the max cell.

function longestCommonSubstring(a, b) {
const m = b.length;
let prev = new Array(m + 1).fill(0), best = 0;
for (let i = 1; i <= a.length; i++) {
const cur = new Array(m + 1).fill(0);
for (let j = 1; j <= m; j++) {
if (a[i - 1] === b[j - 1]) { cur[j] = prev[j - 1] + 1; best = Math.max(best, cur[j]); }
}
prev = cur;
}
return best;
}

2. Is C an interleaving of A and B?

Time O(n·m)Space O(m)

dp[i][j] = can A[..i] + B[..j] form C[..i+j]. dp[i][j] = (A[i−1]===C[i+j−1] && dp[i−1][j]) || (B[j−1]===C[i+j−1] && dp[i][j−1]).

function isInterleave(a, b, c) {
if (a.length + b.length !== c.length) return false;
const dp = new Array(b.length + 1).fill(false);
for (let i = 0; i <= a.length; i++)
for (let j = 0; j <= b.length; j++) {
if (i === 0 && j === 0) dp[j] = true;
else {
const fromA = i > 0 && a[i - 1] === c[i + j - 1] && dp[j];
const fromB = j > 0 && b[j - 1] === c[i + j - 1] && dp[j - 1];
dp[j] = fromA || fromB;
}
}
return dp[b.length];
}

LCS of 3 strings: a 3-D dp[i][j][k]. Space-optimised LCS: keep only the previous row (two 1-D arrays). Boolean parenthesization: interval DP counting the ways an expression of T/F with & | ^ evaluates to true — track (trueCount, falseCount) per interval and combine at each operator.