class Solution {
    public int longestCommonSubsequence(String text1, String text2) {

        // bottom-up solution
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];

        // initilize
        dp[0][0] = 0;
        dp[1][0] = 0;
        dp[0][1] = 0;

        for (int i1 = 1; i1 <= text1.length() ;i1++) {
            for (int i2 = 1; i2 <= text2.length() ;i2++) {

                int len_12 = 0;
                if (text1.charAt(i1 - 1) == text2.charAt(i2 - 1)) {
                    // one more option to do here
                    len_12 = 1 + dp[i1 -1][i2 - 1];
                }

                int len_1 = dp[i1 - 1][i2];
                int len_2 = dp[i1][i2 - 1];

                int len_best = Math.max(len_12, Math.max(len_1, len_2));
                dp[i1][i2] = len_best;
           }
        }

        return dp[text1.length()][text2.length()];

        // top-down solution:
        // return go(text1, text2, 0, 0);
    }

    // top-down solution:
    Map<String, Integer> cache = new HashMap<>();
    int go(String text1, String text2, int i1, int i2) {
        if (i1 == text1.length()) return 0;
        if (i2 == text2.length()) return 0;

        if (cache.containsKey(get_key(i1, i2))) {
            return cache.get(get_key(i1, i2));
        }

        Integer len_12 = 0;
        if (text1.charAt(i1) == text2.charAt(i2)) {
            // one more option to do here
            len_12 = 1 + go(text1, text2, i1 + 1, i2 + 1);
        }

        int len_1 = go(text1, text2, i1 + 1, i2);
        int len_2 = go(text1, text2, i1, i2 + 1);

        int len_best = Math.max(len_12, Math.max(len_1, len_2));

        cache.put(get_key(i1, i2), len_best);

        return len_best;
    }

    String get_key(int i1, int i2) {
        return "("+i1+","+i2+")";
    }

}