Identifying the Simultaneous Traversal Pattern

The Diagnostic Questions

Before deciding this pattern applies, run through these three questions:

If yes to all three, you have a simultaneous traversal problem.

The Example: Subsequence Checker

Problem: Given two strings s and t, return True if s is a subsequence of t.

A string s is a subsequence of t if every character of s appears in t in the same relative order — but not necessarily consecutively.

s = "ace",   t = "abcde"  →  True   (a..c..e all appear in order)
s = "aec",   t = "abcde"  →  False  (e appears before c in t, not after)

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart LR
  subgraph T["t = a b c d e"]
    direction LR
    T0["a"] --- T1["b"] --- T2["c"] --- T3["d"] --- T4["e"]
  end
  subgraph S["s = a · c · e"]
    direction LR
    S0["a"] ~~~ S1["c"] ~~~ S2["e"]
  end
  S0 -->|"matched at t[0]"| T0
  S1 -->|"matched at t[2]"| T2
  S2 -->|"matched at t[4]"| T4

s = "ace" is a subsequence of t = "abcde" — each character of s maps to a later position in t, maintaining order.

Applying the Diagnostic Questions

Q1 — Why “two sequences processed together”?

WHAT: The problem asks whether every character of s appears in t in the same order. You must match characters across both strings simultaneously — you can’t answer this by scanning just s or just t alone.

WHY two cursors are required: index1 tracks “which character of s are we currently trying to find?”, and index2 tracks “where in t are we currently looking?”. Losing track of either position breaks the ordering guarantee.

What breaks with a single pointer: If you had one pointer scanning t for each character of s independently, you’d find ‘a’, ‘c’, ‘e’ correctly — but you’d also incorrectly accept s = "aec" because ‘a’, ‘e’, ‘c’ can each be found in t individually. The single pointer would restart from the beginning of t each time, losing the positional constraint.

Q2 — Why “advancing index1 depends on a comparison”?

WHAT: At every step, index2 always advances (we always move through t). But index1 only advances when s[index1] == t[index2] — when we’ve found the current target character.

WHY this conditional movement is the pattern: The key insight is that t might have many characters that aren’t in s. We skip over them by advancing index2 without touching index1. Only a match triggers progress in s.

Concrete check with s=“ace”, t=“abcde”:

• index1=0 ('a'), index2=0 ('a'): match → advance both
• index1=1 ('c'), index2=1 ('b'): no match → advance only index2
• index1=1 ('c'), index2=2 ('c'): match → advance both
• index1=2 ('e'), index2=3 ('d'): no match → advance only index2
• index1=2 ('e'), index2=4 ('e'): match → advance both
• index1=3 == len(s)=3 → all of s was matched → return True

What breaks without conditional movement: If you advanced index1 regardless of whether there was a match, you’d move through s at the same speed as t, comparing s[0] with t[0], s[1] with t[1], etc. That checks if s is a prefix of t, not a subsequence.

Q3 — Why “simple and deterministic at every step”?

WHAT: The condition is just s[index1] == t[index2] — a single character comparison. No sorting needed, no auxiliary data structure, no lookahead.

WHY this guarantees O(N + M): Because the condition takes O(1) time and each pointer only moves forward, the total number of steps is at most len(s) + len(t). The algorithm never needs to revisit a position in either string.

What would break this guarantee: If the condition required scanning ahead — “does s[index1] appear anywhere in the remaining t?” — you’d need an inner loop, pushing complexity to O(N × M). The simultaneous traversal only works efficiently when the advance decision is local (based on current positions only).

Brute Force: Nested Scan, O(N × M)

For each character in s, scan t from where we left off to find its first occurrence:

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart TB
  Start(["j = 0"])
  ForI["for i in range(len(s))"]
  CheckJ{"j == len(t)?"}
  RetFalse(["return False"])
  WhileJ{"j < len(t)"}
  Match{"s[i] == t[j]?"}
  AdvBoth["j += 1<br/>break"]
  AdvJ["j += 1"]
  RetTrue(["return True"])

  Start --> ForI --> CheckJ
  CheckJ -->|"yes"| RetFalse
  CheckJ -->|"no"| WhileJ
  WhileJ -->|"yes"| Match
  WhileJ -->|"no"| ForI
  Match -->|"yes"| AdvBoth --> ForI
  Match -->|"no"| AdvJ --> WhileJ
  ForI -->|"i exhausted"| RetTrue

Brute force — for each character of s, scan forward in t until found or t is exhausted. Correct, but the nested structure is error-prone.

from typing import List

def is_subsequence_brute(s: str, t: str) -> bool:
    j = 0  # Tracks current position in t across iterations of the outer loop

    # For each character in s, search for it in t starting from where we left off
    for i in range(len(s)):
        if j == len(t):
            # t is exhausted but s still has characters left — can't be a subsequence
            return False

        # Scan t forward until we find s[i] or exhaust t
        while j < len(t):
            if s[i] == t[j]:
                j += 1  # Found s[i] at t[j] — advance t past this match
                break   # Move to the next character in s
            j += 1      # t[j] doesn't match — skip it

    return True  # All characters of s were found in t in order

print(is_subsequence_brute("ace", "abcde"))  # True
print(is_subsequence_brute("aec", "abcde"))  # False

j = 0

i=0, s[0]='a':
  j=0, t[0]='a': 'a'=='a' → j=1, break
i=1, s[1]='c':
  j=1, t[1]='b': 'c'≠'b' → j=2
  j=2, t[2]='c': 'c'=='c' → j=3, break
i=2, s[2]='e':
  j=3, t[3]='d': 'e'≠'d' → j=4
  j=4, t[4]='e': 'e'=='e' → j=5, break

i exhausted → return True ✓

Note: j never resets to 0 — this version actually behaves like simultaneous traversal
      under the hood. The nested while loop is what makes it hard to read and reason about.

Simultaneous Traversal Solution: One Loop, O(N + M)

The same logic, expressed cleanly with two explicit index variables:

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart LR
  subgraph Step0["Start: index1=0 ('a'), index2=0 ('a')"]
    direction LR
    SA0["a"] --- SA1["c"] --- SA2["e"]
    TA0["a"] --- TA1["b"] --- TA2["c"] --- TA3["d"] --- TA4["e"]
    P1A(["i1=0"]) --> SA0
    P2A(["i2=0"]) --> TA0
  end
  subgraph Step1["Match 'a': advance both → index1=1, index2=1"]
    direction LR
    SB0["✓a"] --- SB1["c"] --- SB2["e"]
    TB0["✓a"] --- TB1["b"] --- TB2["c"] --- TB3["d"] --- TB4["e"]
    P1B(["i1=1"]) --> SB1
    P2B(["i2=1"]) --> TB1
  end
  subgraph Step2["No match 'c'≠'b': advance index2 only → index2=2"]
    direction LR
    SC0["✓a"] --- SC1["c"] --- SC2["e"]
    TC0["✓a"] --- TC1["b"] --- TC2["c"] --- TC3["d"] --- TC4["e"]
    P1C(["i1=1"]) --> SC1
    P2C(["i2=2"]) --> TC2
  end
  Step0 -->|"'a'=='a' match"| Step1
  Step1 -->|"'c'≠'b' no match"| Step2

Simultaneous traversal — index2 always advances; index1 only advances on a match. The two-pointer structure makes the logic explicit and easy to follow.

from typing import List

class Solution:
    def subsequence_checker(self, s: str, t: str) -> bool:
        index1 = 0  # Points at the current character in s we're trying to find in t
        index2 = 0  # Points at the current character in t we're examining

        # Run while both strings have unexamined characters
        while index1 < len(s) and index2 < len(t):
            if s[index1] == t[index2]:
                # Found the current target character from s — move s's pointer forward
                index1 += 1
            # Always advance t's pointer — we examine every character of t exactly once
            index2 += 1

        # If index1 reached the end of s, all characters were matched in order
        # If index1 < len(s), t ran out before all of s was matched
        return index1 == len(s)


print(Solution().subsequence_checker("ace", "abcde"))  # True
print(Solution().subsequence_checker("aec", "abcde"))  # False
print(Solution().subsequence_checker("", "abcde"))     # True  (empty string is always a subsequence)
print(Solution().subsequence_checker("abc", ""))       # False (non-empty s can't match empty t)

index1 = 0,  index2 = 0

Step 1 │ index1=0 ('a'), index2=0 ('a') │ 'a'=='a' match  │ index1=1, index2=1
Step 2 │ index1=1 ('c'), index2=1 ('b') │ 'c'≠'b' no match│ index1=1, index2=2
Step 3 │ index1=1 ('c'), index2=2 ('c') │ 'c'=='c' match  │ index1=2, index2=3
Step 4 │ index1=2 ('e'), index2=3 ('d') │ 'e'≠'d' no match│ index1=2, index2=4
Step 5 │ index1=2 ('e'), index2=4 ('e') │ 'e'=='e' match  │ index1=3, index2=5
Step 6 │ index1=3 == len(s)=3 → loop exits

Return: index1 == len(s) → 3 == 3 → True ✓

Failure case — s = "aec", t = "abcde":
Step 1 │ index1=0 ('a'), index2=0 ('a') │ match   │ index1=1, index2=1
Step 2 │ index1=1 ('e'), index2=1 ('b') │ no match│ index1=1, index2=2
Step 3 │ index1=1 ('e'), index2=2 ('c') │ no match│ index1=1, index2=3
Step 4 │ index1=1 ('e'), index2=3 ('d') │ no match│ index1=1, index2=4
Step 5 │ index1=1 ('e'), index2=4 ('e') │ match   │ index1=2, index2=5
Step 6 │ index2=5 == len(t)=5 → loop exits

Return: index1 == len(s) → 2 == 3 → False ✓
Note: 'e' was found before 'c', so s[2]='c' was never matched — index1 stopped at 2.

Problems in This Category

The difficulty varies by how complex the advance condition is — but the template stays the same.