CommonCharacters

CommonCharacters.java

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    static Map<Character, Set<Integer>> s1Map = new TreeMap<>();
    static Map<Character, Set<Integer>> s2Map = new TreeMap<>();

    static void fillMap(String str, Map<Character, Set<Integer>> map) {
        for (int i = 0; i < str.length(); i++)
        {
            char c = str.charAt(i);
            if (!map.containsKey(c))
            {
                map.put(c, new TreeSet<Integer>());
            }

            map.get(c).add(i);
        }
    }

    static void clean(Map<Character, Set<Integer>> a, Map<Character, Set<Integer>> b)
    {
        common = new TreeSet<>();

        for (Character c : a.keySet()) {
            if (b.containsKey(c))
                common.add(c);
        }

/*
        Set<Character> tmp = new TreeSet(a.keySet());

        for (Character c : tmp)
        {
            if (!common.contains(c))
                a.remove(c);
        }

        tmp = new TreeSet(b.keySet());

        for (Character c : tmp)
        {
            if (!common.contains(c))
                b.remove(c);
        }
        */
    }

    static Map<String, Integer> cache = new HashMap<>();
    static Set<Character> common;

    static int getMax(String main, int al, int bl) {

        if (al >= la || bl >= lb)
            return 0;

        String key = al + "-" + bl;
        Integer cached = cache.get(key);
        if (cached != null)
            return cached;

        Character c = main.charAt(al);
        
        if (!common.contains(c))
        {
            int v = getMax(main, al + 1, bl); //Next char
            //cache.put(key, v);
            return v;         
        } 

        Set<Integer> bset = s2Map.get(c);
        Integer newBL = ((TreeSet<Integer>) bset).higher(bl-1);

        int include = newBL != null ? 1 + getMax(main, al + 1, newBL + 1) : 0;
        int skip = getMax(main, al + 1, bl);

        int val = Math.max(include, skip);
        cache.put(key, val);
        
        return val;         
    }


    //al = aLocation
    //la = length of a 
    static int la, lb;
    static int al, bl;
    static int getMax(String s1, String s2)
    {
        fillMap(s1, s1Map);
        fillMap(s2, s2Map);

        clean(s1Map, s2Map);
        
        la = s1.length();
        lb = s2.length();
        int maxA = getMax(s1, 0, 0);
        //int maxB = getMax(s2, 0, 0, s2Map, s1Map);

        return maxA;
        //return Math.max(maxA,maxB);
    }

    // Complete the commonChild function below.
    static int commonChild(String s1, String s2) {
        int r = getMax(s1,s2);
        return r;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String s1 = scanner.nextLine();

        String s2 = scanner.nextLine();

        int result = commonChild(s1, s2);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedWriter.close();

        scanner.close();
    }
}