Space Optimized Solution of LCS

Problem Statement

Find the length of the Longest Common Subsequence (LCS) of two strings, but using only O(min(m, n)) space instead of the usual O(m × n) 2D table.

Example:

• Input: s1 = "ABCBDAB", s2 = "BDCAB"
• Output: 4 (LCS is "BCAB" or "BDAB")

Noob-Friendly Explanation

Remember the LCS problem where we use a big 2D grid? If the strings are very long (say 10,000 characters each), that grid needs 100 million cells — too much memory! But here's the trick: when filling the grid, each row only needs the row above it. So we can use just two rows (or even one row with a trick) instead of the whole grid. Same answer, way less memory!

Approach 1: Brute Force (Standard 2D DP)

Intuition

The classic LCS approach using a full 2D table. This works but uses O(m × n) space.

Algorithm

1. Create dp[m+1][n+1] initialized to 0
2. Fill using standard LCS recurrence
3. Answer is dp[m][n]

public class Solution {
    public int lcs(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[m][n];
    }
}

Complexity Analysis

• Time Complexity: O(m * n) - Fill each cell of the table
• Space Complexity: O(m * n) - Full 2D table

Approach 2: Optimal (Space-Optimized 1D DP)

Intuition

When computing row i, we only need values from row i-1. So we use a single 1D array and update it carefully. We keep a variable prev to store the diagonal value that would otherwise be overwritten.

Algorithm

1. Make sure we iterate over the shorter string in the inner loop (use min(m,n) space)
2. Use a single array dp of size min(m, n) + 1
3. For each character in the longer string, update dp left to right, saving the diagonal value before overwriting

public class Solution {
    public int lcs(String s1, String s2) {
        // Ensure s2 is the shorter string for space optimization
        if (s1.length() < s2.length()) {
            String temp = s1;
            s1 = s2;
            s2 = temp;
        }

        int m = s1.length();
        int n = s2.length();
        int[] dp = new int[n + 1];

        for (int i = 1; i <= m; i++) {
            int prev = 0; // stores dp[i-1][j-1]
            for (int j = 1; j <= n; j++) {
                int temp = dp[j]; // save current before overwriting

                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[j] = prev + 1;
                } else {
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }

                prev = temp; // diagonal for next iteration
            }
        }

        return dp[n];
    }
}

Complexity Analysis

• Time Complexity: O(m * n) - Same as 2D approach, we still check every pair
• Space Complexity: O(min(m, n)) - Only one 1D array of the shorter string's length