Longest Common Subsequence

Given two sequences, find the length of longest subsequence present in both of them. Both the strings are of uppercase.

• Time : O(xy)
• Space : O(min(x,y))

class Solution {
public:
    //Function to find the length of longest common subsequence in two strings.
    int lcs(int x, int y, string s1, string s2) {
        if(x < y) return lcs(y, x, s2, s1);
        vector<int> dp(y + 1);

        for(int i = 1; i <= x; i++) {
            vector<int> ndp(y + 1);
            for(int j = 1; j <= y; j++) {
                if(s1[i-1] == s2[j-1]) ndp[j] = dp[j-1] + 1;
                else ndp[j] = max(dp[j], ndp[j-1]);
            }
            swap(ndp, dp);
        }

        return dp[y];
    }
};