Java Binary Search (Explanation)
First, we store all characters\' positions of input. \nFor example: input = "abacbca" ---> POS = [\'a\', \'b\', \'c\'] = [ [0,2,6], [1,4], [3,5] ]\n\n- Second, 
- First, we store all characters\' positions of input. \nFor example: ```input = "abacbca"``` ---> ```POS = [\'a\', \'b\', \'c\'] = [ [0,2,6], [1,4], [3,5] ]```\n\n- Second, while iterating ```words```, for **each character** of **each word**, we check if we can choose a position from **POS**, and the position must follow an increasing order.\nFor example: ```word = "acb"```\n```\'a\'``` we choose ```0```\n```\'c\'``` we choose ```3```\n```\'b\'``` we choose ```4```\n```[0,3,4]``` is an increasing order, so ```"acb"``` is a subsequence of our input.\n\n- Third, we store the position of current iterating character in a variable ```cur```. The next iteration, we will chose the position so that it\'s value > ```cur``` by using **Binary Search**\n\n```\n\tpublic int numMatchingSubseq(String s, String[] words) {\n        int res = 0, cur, i;\n        List<Integer>[] pos = positions(s);\n        for (String w : words) {\n            for (i = 0, cur = 0; i < w.length(); i++, cur++) {\n                char c = w.charAt(i);\n                cur = search(pos[c-\'a\'], cur);\n                if (cur == -1) break;\n            }\n            if (cur != -1) res++;\n        }\n        return res;\n    }\n\t\n    private List<Integer>[] positions(String s) {\n        List<Integer>[] pos = new List[\'z\'-\'a\'+1];\n        for (int i = 0; i < s.length(); i++) {\n            char c = s.charAt(i);\n            if (pos[c-\'a\'] == null) pos[c-\'a\'] = new ArrayList<>();\n            pos[c-\'a\'].add(i);\n        }\n        return pos;\n    }\n\t\n\tprivate int search(List<Integer> ns, int n) {\n        if (ns == null) return -1;\n        int lo = 0, hi = ns.size()-1;\n        if (ns.get(lo) >= n) return ns.get(lo);\n        if (ns.get(hi) < n) return -1;\n        while (lo < hi) {\n            int mi = (lo + hi)/2;\n            if (ns.get(mi) == n) return ns.get(mi);\n            if (ns.get(mi) < n) lo = mi+1;\n            else hi = mi;\n        }\n        return ns.get(hi);\n    }\n```\n\nTime complexity is ``` O(mklog(n) ``` where \n\t```n``` is the length of ```s```, \n\t```m``` is the length of ```words```, \n\t```k``` is the largest length of ```word```.
[]