Longest Common Subsequence

class Solution {
public:
    int longestCommonSubsequence(string a, string b) {
        int n = a.size(), m = b.size();
        vector<int> dp(m + 1, 0);
        for (int i = 1; i <= n; ++i) {
            int prev = 0;
            for (int j = 1; j <= m; ++j) {
                int temp = dp[j];
                if (a[i - 1] == b[j - 1]) dp[j] = prev + 1;
                else dp[j] = max(dp[j], dp[j - 1]);
                prev = temp;
            }
        }
        return dp[m];
    }
};

func longestCommonSubsequence(a string, b string) int {
    n, m := len(a), len(b)
    dp := make([]int, m+1)
    for i := 1; i <= n; i++ {
        prev := 0
        for j := 1; j <= m; j++ {
            temp := dp[j]
            if a[i-1] == b[j-1] {
                dp[j] = prev + 1
            } else if dp[j-1] > dp[j] {
                dp[j] = dp[j-1]
            }
            prev = temp
        }
    }
    return dp[m]
}

class Solution:
    def longestCommonSubsequence(self, a: str, b: str) -> int:
        n, m = len(a), len(b)
        dp = [0] * (m + 1)
        for i in range(1, n + 1):
            prev = 0
            for j in range(1, m + 1):
                temp = dp[j]
                if a[i - 1] == b[j - 1]:
                    dp[j] = prev + 1
                else:
                    dp[j] = max(dp[j], dp[j - 1])
                prev = temp
        return dp[m]

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

class Solution {
    public int longestCommonSubsequence(String a, String b) {
        int n = a.length(), m = b.length();
        int[] dp = new int[m + 1];
        for (int i = 1; i <= n; i++) {
            int prev = 0;
            for (int j = 1; j <= m; j++) {
                int temp = dp[j];
                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    dp[j] = prev + 1;
                } else {
                    dp[j] = Math.max(dp[j], dp[j - 1]);
                }
                prev = temp;
            }
        }
        return dp[m];
    }
}

function longestCommonSubsequence(a: string, b: string): number {
    const n = a.length, m = b.length;
    const dp: number[] = new Array(m + 1).fill(0);
    for (let i = 1; i <= n; i++) {
        let prev = 0;
        for (let j = 1; j <= m; j++) {
            const temp = dp[j];
            if (a[i - 1] === b[j - 1]) {
                dp[j] = prev + 1;
            } else {
                dp[j] = Math.max(dp[j], dp[j - 1]);
            }
            prev = temp;
        }
    }
    return dp[m];
}