Longest Common Subsequence

• Time : O(nm)
• Space : O(nm)

#include <vector>
using namespace std;

vector<char> longestCommonSubsequence(string str1, string str2) {
  int n = str1.length(), m = str2.length();
	vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
	vector<vector<pair<int,int>>> path(n + 1, vector<pair<int,int>>(m + 1));
	
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j<= m; j++) {
			if(str1[i-1] == str2[j-1]) {
				dp[i][j] = dp[i-1][j-1] + 1;
				path[i][j] = {-1, -1};
			} else {
				if(dp[i-1][j] > dp[i][j-1]) {
					dp[i][j] = dp[i-1][j];
					path[i][j] = {-1,0};
				} else {
					dp[i][j] = dp[i][j-1];
					path[i][j] = {0,-1};
				}
			}
		}
	}
	
	int y = n, x = m;
	vector<char> res;
	while(true) {
		auto [py, px] = path[y][x];
		if(py == 0 and px == 0) break;
		if(py == -1 and px == -1) {
			res.push_back(str1[y-1]);
		}
		y += py;
		x += px;
	}
	
	reverse(begin(res),end(res));
	
  return res;
}