String DP — longest common substring, LCS of three strings, space-optimised LCS, interleaving, boolean parenthesization
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
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.