#ifndef LONGEST_COMMON_SUBSEQUENCE_H
#define LONGEST_COMMON_SUBSEQUENCE_H

#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    auto longestCommonSubsequence(const string &text1, const string &text2)->int {
        vector<vector<long long>> dp(text1.size() + 1, vector<long long>(text2.size() + 1, 0));

        long long ans = 0;
        for (int i = 1; i <= text1.size(); i++) {
            for (int j = 1; j <= text2.size(); j++) {
                if (text1[i - 1] == text2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
                ans = max(ans, dp[i][j]);
            }
        }

        return ans;
    }
};

#endif