Is a short route hidden inside a long one?

Two pointers Junior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
short, long_ = "ace", "abcde"
i = 0
for ch in long_:
    if i < len(short) and ch == short[i]:
        i += 1
print(i == len(short), i)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A True 3

Right: a, c and e are matched in order.

The pointer only advances on a match, so it ends at the number of short stops found in order.

Why not the others?
  • B False 2. e is matched at the end of the long route.
  • C True 5. i counts matched short stops, not long stops.

30-second answer

Walk the long route once with a pointer into the short route. Whenever the current long stop equals the next needed short stop, advance the short pointer. If it reaches the end, the short route is hidden inside. O(n) time for a long route of length n, O(1) space.

Practise saying it · 30 s. No recording, just a timer

Explain the greedy check for a hidden route.

Say your answer out loud, then check which of these points you covered:

  • One pointer per string
  • Greedy earliest match
  • O(n) time, O(1) space

Deep dive

Greedy matching is safe: taking the earliest possible match never hurts, because it leaves the most route for the remaining stops.

An empty short route is always hidden inside, including in an empty long route.

For many short routes against one long route, precompute for each letter the sorted positions and binary search: O(k log n) per query.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def hidden_inside(short: str, long_route: str) -> bool:
    i = 0
    for stop in long_route:
        if i < len(short) and stop == short[i]:
            i += 1
    return i == len(short)

Common mistakes

  • Requiring the stops to be contiguous, which is a substring check, not this.
  • Advancing the short pointer on a mismatch.

Senior take & follow-ups

Mention why greedy is correct in one line; interviewers often ask.

Follow-up questions

Think of your answer first, then open the hint.

  1. How would you answer a million queries against one long route?

    Show hint

    Index positions per letter and binary search the next position after the current one.

  2. How do you find the longest common hidden route of two routes?

    Show hint

    That is dynamic programming over both strings, O(n·m).

What each operation costs: Arrays · Array Operations

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.