392. Is Subsequence

/**
 * Using 2 indexes. This solution is good for cases when everytime string t is
 * different. If T is same and different s strings are passed, check the below
 * binary search function.
 *
 * Time Complexity: O(T)
 *
 * Space Complexity: O(1)
 *
 * T = length of string t
 */
class Solution {
    public boolean isSubsequence(String s, String t) throws IllegalArgumentException {
        if (s == null || t == null) {
            throw new IllegalArgumentException("Input string is null");
        }
        if (s.length() == 0) {
            return true;
        }
        if (s.length() > t.length()) {
            return false;
        }

        int indexS = 0;
        for (int indexT = 0; indexT < t.length(); indexT++) {
            if (s.charAt(indexS) == t.charAt(indexT)) {
                indexS++;
            }
            if (indexS == s.length()) {
                return true;
            }
        }

        return false;
    }
}

/**
 * Preprocess T and use Binary Search to check for isSubsequence.
 *
 * Preporcessing Time Complexity: O(T)
 *
 * Time Complexity of isSubsequence: O(S log(T))
 *
 * Space Complexity: O(T)
 *
 * T = length of string t
 */
class Solution {
    public boolean isSubsequence(String s, String t) throws IllegalArgumentException {
        if (s == null || t == null) {
            throw new IllegalArgumentException("Input string is null");
        }
        if (s.length() == 0) {
            return true;
        }
        if (s.length() > t.length()) {
            return false;
        }

        Map<Character, List<Integer>> charMapT = processStr(t);

        int prevIdx = -1;

        for (char c : s.toCharArray()) {
            if (!charMapT.containsKey(c)) {
                return false;
            }
            int nextIdx = binarySearchInList(charMapT.get(c), prevIdx);
            if (nextIdx == -1) {
                return false;
            }
            prevIdx = nextIdx;
        }
        return true;
    }

    private Map<Character, List<Integer>> processStr(String s) {
        Map<Character, List<Integer>> map = new HashMap();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!map.containsKey(c)) {
                map.put(c, new ArrayList<Integer>());
            }
            map.get(c).add(i);
        }
        return map;
    }

    private int binarySearchInList(List<Integer> list, int prev) {
        int start = 0;
        int end = list.size() - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (list.get(mid) <= prev) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return list.get(start) > prev ? list.get(start) : -1;
    }
}