My solution using index, optimized for follow up

• I found most top viewed solutiosn here use two pointers, which scans t at least one time for each given input s. It becomes expensive when calling multiple times for one long t.

The solution below stores characters in t into an index of positions. And for each char c in input s, it finds the smallest possible position and keep searching for the next ones until finish scanning s or no results.

Thus we can only scan string t only once.

public class Solution {
public boolean isSubsequence(String s, String t) {
List<List<Integer>> bucket = new ArrayList<List<Integer>>(26);
for (int i = 0; i < 26; i++) {
}

for (int i = 0; i < t.length(); i++) {
char c = t.charAt(i);
}

int lastPos = -2;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
lastPos = bSearchNext(bucket.get(c - 'a'), lastPos);
if (lastPos == -1) {
return false;
}
}

return true;
}

// find the right next value bigger than target, -1 if no found. Check LC35.
private int bSearchNext(List<Integer> nums, int target) {
if (nums.isEmpty() || nums.get(nums.size() - 1) <= target) {
return -1;
}

int begin = 0;
int end = nums.size() - 1;
while (begin <= end) {
int mid = (begin + end) / 2;
if (nums.get(mid) == target) {
return nums.get(mid + 1);
} else if (nums.get(mid) < target) {
begin = mid + 1;
} else {
end = mid - 1;
}
}

return nums.get(begin);
}
}

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