# A possible solution regarding to "t is very long" and the follow up "lots of incoming S"

• I think this basic idea is to reuse string T and make the complexity of each query of S mainly dominated by the length of S. Here is the summary of my solution:

1. We record the position indexs of every letter appearing in T separately and naturally in ascending order. (This only need to be done once for multiple queries.)
2. For an incoming S, we iterate through every char in S. For char S[i], we go to its position index list and see if we can find a feasible index, i.e., a position that is beyond the position chose for S[i-1] (maintained by endPos). If yes, we update endPos and move to S[i+1]; otherwise, we fail.
3. Further improvement: We can accelerate the creation of index lists from T by using paralleling processing. Every machine is responsible for a part of T and generate a paritial index lists. After all machines finish, we merge those partial index lists together, which is actually easy.

Here is the code:

``````public class Solution {
// Position index list for each letter appearing in t.
// These lists can be reused for multiple queries with different input string s.
List<List<Integer>> charIndexLists = new ArrayList<List<Integer>>();

public boolean isSubsequence(String s, String t) {
// Create position index list for each letter in t.
// IMPORTANT: This part only need to be done ONCE for multiple queries.
for (int i=0;i<26;i++){
}
char[] tCharArr = t.toCharArray();
for (int i=0;i<t.length();i++){
}

// Check if we can find a feasible sequence of indexs in charIndexLists mathcing to s.
char[] sCharArr = s.toCharArray();
int[] pLists = new int[26];
int endPos = -1;
for (int i=0;i<s.length();i++){
// Find out the next available position of current char, i.e.,
// sCharArr[i] should appeear somewhere after endPos.
int curIndex = sCharArr[i]-'a';
List<Integer> curIndexList = charIndexLists.get(curIndex);
while (pLists[curIndex] < curIndexList.size() && curIndexList.get(pLists[curIndex]) <= endPos){
pLists[curIndex]++;
}
// Cannot find any required char that appears after endPos, fails
if (pLists[curIndex] == curIndexList.size()){
return false;
}
// Update endPos.
endPos = curIndexList.get(pLists[curIndex]);
}
return true;
}
}``````

• @shili30205 Same idea as my 1st attempt, the inner while loop can be convert to a binary search, which is more efficient.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.