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?
My solution is to pre-compute an index. The index is built as a linked list. Each node is as follows (in Python style):
class ListNode(object): def __init__(self, letter): self.val = letter # a letter self.next_a = None # link to the ListNode of next 'a' self.next_b = None # link to the ListNode of next 'b' ...... self.next_z = None # link to the ListNode of next 'z'
Process all the letters in T to build this index. This can be done in O(len(T)) time and O(len(T)) space (using DP). Then, for each Si, the execution time is O(len(Si)).
The following is an illustration, where we suppose 'a', 'b', 'c' are all possible letters.