686 Repeated String Match

class Solution {
    public int repeatedStringMatch(String A, String B) {
        StringBuilder sb = new StringBuilder();
        int count = 0;
        while (sb.length() < B.length()){
            sb.append(A);
            count++;
        }

        if (sb.toString().contains(B)) return count;
        if (sb.append(A).toString().contains(B)) return ++count;

        return -1;
    }
}

392. Is Subsequence

class Solution {
    public boolean isSubsequence(String s, String t) {
        int index1 = 0, index2 = 0;

        while (index1 < s.length() && index2 < t.length()){
            char c1 = s.charAt(index1);
            char c2 = t.charAt(index2);

            if (c1 == c2){
                index1++;
                index2++;
            }
            else{
                index2++;
            }
        }

        return index1 == s.length();
    }
}

Follow up:

If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

/**
 * Follow-up
 * If we check each sk in this way, then it would be O(kn) time where k is the number of s and t is the length of t. 
 * This is inefficient. 
 * Since there is a lot of s, it would be reasonable to preprocess t to generate something that is easy to search for if a character of s is in t. 
 * Sounds like a HashMap, which is super suitable for search for existing stuff. 
 */
public boolean isSubsequence(String s, String t) {
    if (s == null || t == null) return false;

    Map<Character, List<Integer>> map = new HashMap<>(); //<character, index>

    //preprocess t
    for (int i = 0; i < t.length(); i++) {
        char curr = t.charAt(i);
        if (!map.containsKey(curr)) {
            map.put(curr, new ArrayList<Integer>());
        }
        map.get(curr).add(i);
    }

    int prev = -1;  //index of previous character
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);

        if (map.get(c) == null)  {
            return false;
        } else {
            List<Integer> list = map.get(c);
            prev = binarySearch(prev, list, 0, list.size() - 1);
            if (prev == -1) {
                return false;
            }
            prev++;
        }
    }

    return true;
}

private int binarySearch(int index, List<Integer> list, int start, int end) {
    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (list.get(mid) < index) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }

    return start == list.size() ? -1 : list.get(start);
}

395. Longest Substring with At Least K Repeating Characters

class Solution {
    public int longestSubstring(String s, int k) {
        if (s == null || s.length() == 0 || k == 0) return 0;
        int[] count = new int[26];

        for (char c : s.toCharArray()){
            count[c - 'a']++;
        }

        List<Integer> pos = new ArrayList<>();
        for (int i = 0; i < s.length(); i++){
            if (count[s.charAt(i) - 'a'] < k) pos.add(i);
        }

        if (pos.size() == 0) return s.length();
        int res = 0;
        pos.add(0, -1);
        pos.add(s.length());
        for (int i = 1; i < pos.size(); i++){
            int start = pos.get(i - 1) + 1;
            int end = pos.get(i);
            int next = longestSubstring(s.substring(start, end), k);
            res = Math.max(res, next);
        }

        return res;
    }
}