Why it works
- Taking the first matching letter of t is never worse than taking a later one: whatever fits after a later match also fits after the earlier one, because more of t is left.
- A letter of t that is not the one we look for is of no use later either: the next letters of s have to come after the current one, and this letter is before it.
- If i reaches the end of s, every letter is found in order: yes. If t runs out first, a letter of s has no place after the ones before it: no.
Complexity
Time O(n), where n is the length of t: j moves one letter every step, so the loop runs at most n times. Memory O(1): only two indices.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗