string contains all chars ordered

🏠

Checking whether string a contains all the characters in string b in order can be done in O(n)time and succinctly in python, by using an iterator.

1 st = iter('hello')
2 ar = 'el'
3 print(all(c in st for c in ar))

This works because calling in on an iterator will continue calling it.next() until the item is met.

Therefore, iterating takes O(|a|) and there will be O(max(|a|, |b|)) comparisons.

Time complexity: O(n)

See also:

string contains all chars unordered