Is Subsequence
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Check whether s can be made from t by deleting some characters of t without reordering.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Scan the long text once. When do you move forward in the short one?
- Hint 2Take the earliest match each time; it never hurts.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
You carry a shopping list: milk, eggs, bread (in that order, as the shop is laid out). You walk through the market and tick an item the first time you see it. If you reach the end of the market with every item ticked, your list was a subsequence of the market. You never walk back.
- The obvious way
Try all subsequences of t: exponential.
- The key insight
Greedy works: always match the next item of s at the first chance in t, because an earlier match leaves at least as much text for the rest. One walk with a pointer into s; if it reaches the end of s, the answer is yes.
- The algorithm
- Point at the first item of the short text s.
- Walk through the long text t, one character at a time.
- If the character equals the item you are looking for, tick it: move to the next item of s.
- At the end, ticked everything? Answer True.
Watch it run
Examples = "abc", t = "ahbgdc"
Looking for a. The market's first item is a: tick it. Now looking for b.
ticked: a
Where people slip
- If s is empty the answer is True.
- For many queries against one t, precompute each character's positions and binary search.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def is_subsequence(short, long):
wanted = 0 # which item of short we look for
for character in long:
if wanted < len(short) and character == short[wanted]:
wanted += 1 # tick it
return wanted == len(short)Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.