String Reverse Traversal (suffix, backward scan)

Reverse traversal walks from the end—for i in range(len(s)-1, -1, -1) or for ch in reversed(s). Useful for suffix properties, trimming trailing spaces, or propagating constraints backward.

Why this shows up in the real world

File path cleanup may strip trailing slashes by scanning backward. Dynamic programming on strings often fills tables from right to left.

Core idea (explained for students)

Pattern: maintain suffix_ok[i] by iterating i downward. Pair with forward pass when you need both prefix and suffix minima.

Try this in Python

def last_index_of_each(s: str) -> dict[str, int]:
    last: dict[str, int] = {}
    for i in range(len(s) - 1, -1, -1):
        if s[i] not in last:
            last[s[i]] = i
    return last


print(last_index_of_each("abac"))

Common mistakes

• Off-by-one when mixing forward and reverse index math in one formula.
• Empty string: range(-1, -1, -1) is empty—good, but guard len==0 early for clarity.

Key takeaways

• Draw indices 0..n-1 on paper when mixing directions.
• reversed(range(n)) is readable shorthand.