# The Line Cutter

> Did everyone with an A-pass get through before the B-crowd arrived?

Canonical URL: <https://datadriven.io/problems/the_line_cutter>

Domain: Python · Difficulty: easy · Seniority: L3

## Problem

Given a string s and two distinct characters a and b, return True if every occurrence of a precedes every occurrence of b (i.e., the last index of a is before the first index of b). If either character is absent, return True.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **string scanning and ordering constraints**. It reveals whether a candidate can express a simple ordering invariant (all `a` before all `b`) without overcomplicating the logic with nested loops or sorting.

---

### Break down the requirements

#### Step 1: Find the last occurrence of character a

Scan the string to find the rightmost index where `a` appears. If `a` is absent, the constraint is trivially satisfied.

#### Step 2: Find the first occurrence of character b

Scan to find the leftmost index where `b` appears. If `b` is absent, the constraint is trivially satisfied.

#### Step 3: Compare the two positions

If the last `a` comes before the first `b`, every `a` precedes every `b`. Otherwise, at least one `a` appears after a `b`.

---

### The solution

**Last-a vs first-b index comparison**

```python
def check_order(s, a, b):
    last_a = -1
    first_b = len(s)
    for i in range(len(s)):
        if s[i] == a:
            last_a = i
        if s[i] == b and i < first_b:
            first_b = i
    return last_a < first_b
```

> **Time and Space Complexity**
>
> **Time:** O(n) with a single pass through the string.
> 
> **Space:** O(1). Only two index variables are stored.

> **Interviewers Watch For**
>
> Can you reduce this to a single pass? Candidates who write two separate loops are correct but miss the elegance of tracking both indices simultaneously.

> **Common Pitfall**
>
> Returning `True` only when both characters are present. The problem states that missing characters should return `True`, so the default values (`-1` and `len(s)`) must handle that case.

---

## Common follow-up questions

- What if you had three characters that all needed to be in order? _(Tests generalizing to a chain of ordering constraints.)_
- What if the check needed to be case-insensitive? _(Tests string normalization before comparison.)_
- How would you return the first violating index instead of a boolean? _(Tests modifying the scan to track the violation point.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_line_cutter)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.