class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        return go(text1, text2, 0, 0);
    }

    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+")";
    }

}