/**
* Followup
* 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);
}
Java code for the followup question


@theklam Yes. You are right. Since we always need to move forward in
t
regarding the index, thus we have to find out the very first character int
that is the same with the current character we are considering ins
. Then we set ourprev
(which is the start index of substring int
) toprev++
.

@YaokaiYang said in Java code for the followup question:
Yes. You are right. Since we always need to move forward in t regarding the index, thus we have to find out the very first character in t that is the same with the current character we are considering in s. Then we set our prev (which is the start index of substring in t) to prev++.
Great explanation. Thanks for sharing the binary search solution

So what is the time complexity of this solution?
For the worst case, t should be like "aaa....aaa" with the length N, the binary search is O(logN), suppose the average length of the incoming strings is M, and the number of incoming strings is K, the total runtime would be O(MKlogN).
Am I right?

@zhangruoxi Yes. I think that's the runtime complexity, considering we are doing a binary search for every character in the incoming strings.