11b0111c0122d0122e0123

When filling in we have 2 cases

if (text1.charAt(i) == text2.charAt(j)), then we do 1 + dp[i-1][j-1]:

For e.g. filing in i = 1, j = 1 (for char a in text1 and text2), marked in green, and prev value in orange: $$ \begin{matrix} . & Ø & a & c & e \\ Ø & \colorbox{orange} 0 & 0 & 0 & 0 \\ a & 0 & \colorbox{lightgreen} 1 & 1 & 1 \\ ... \end{matrix} $$

if (text1.charAt(i) != text2.charAt(j)) then we filling using Math.max(dp[i - 1][j], dp[i][j - 1])

For eg. i = 1, j = 2 (marked green), it takes marked in orange.:

$$ \begin{matrix} . & Ø & a & c & e \\ Ø & 0 & 0 & \colorbox{orange} 0 & 0 \\ a & 0 & \colorbox{orange} 1 & \colorbox{lightgreen} 1 & 1 \\ ... \end{matrix} $$

Method 4 - Space Optimized Bottom up DP

The key observation in previous approach is that each iteration only needs previous row values. We can leverage this by using just two rows (dp[2][n+1]) instead of the entire table (dp[m+1][n+1]), reducing memory usage significantly. See the updated implementation below.

Instead of maintaining a table of size (m+1) x (n+1), we reduce the space to 2 rows of size (n+1).
These 2 rows alternate between representing the "current row" and "previous row":
- For the current DP row, use dp[i % 2].
- For the previous DP row, use dp[(i-1) % 2].

Approach

Space Reduction:
- Instead of creating a 2D dp table of size (m+1) x (n+1), create a dp array of size 2 x (n+1).
- These two rows are alternated during the computation.
Row Alternation:
- For each character in text1 (indexed by i), compute the results row by row.
- Use i % 2 for the current row and (i-1) % 2 for the previous row. This alternation allows us to reuse space while maintaining correctness.
Character Match:
- If text1[i-1] == text2[j-1], update dp[i % 2][j] = dp[(i-1) % 2][j-1] + 1. Add 1 to the diagonal value since this character contributes to the LCS.
Character Mismatch:
- If text1[i-1] != text2[j-1], take the maximum of the two possibilities:
  - dp[(i-1) % 2][j] (skipping the current character in text1).
  - dp[i % 2][j-1] (skipping the current character in text2).
- Update dp[i % 2][j] to be the maximum of these values.
Final Result:
- After iterating through both strings, the LCS length is stored in dp[m % 2][n].

Code

[{"language":"Java","code":"class Solution {\n    public int longestCommonSubsequence(String text1, String text2) {\n\t\tint m = text1.length();\n\t\tint n = text2.length();\n\t\tint[][] dp = new int[2][n + 1];\n\t\t// no need to start from i and j = 0, as default value is 0\n        for (int i = 1; i <= m; i++) {\n            for (int j = 1; j <= n; j++) {\n                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {\n\t                dp[i % 2][j] = 1 + dp[(i - 1) % 2][j - 1];\n                }\n

Related Tags