0

Longest substring without three repeats in a row

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Longest substring without three repeats in a row

Companies: Microsoft

Difficulty: Medium

Problem statement

Given a string s, return the length of the longest substring of s in which no character appears three or more times in a row. Call such a substring semi-alternating: runs of one or two equal characters are fine, but a run of three is not.

Implement:

def longest_semi_alternating(s: str) -> int

A substring is a contiguous slice of s. Return 0 for the empty string.

Constraints

  • 0 <= len(s) <= 2 * 10^5
  • s may contain any characters (letters, digits, symbols), not only two letters.
  • Aim for O(n) time and O(1) extra space.

Example 1

s = "kkkhhkkkhh"
output: 6

The triple kkk appears twice. The longest stretch that avoids both is "kkhhkk" (indices 1 to 6).

Example 2

s = "ppqqpp"
output: 6

Every run has length at most two, so the whole string counts.

Interviewers often follow up by asking for the substring itself, a general limit of k repeats, or the number of valid substrings.

Approach

A substring is valid exactly when no run of equal characters inside it is
longer than two. So the only thing that can break a window is a third copy
of the same character in a row.

Brute force. Check every substring and scan it for xxx. That is
O(n^3), or O(n^2) if you extend each start until the first bad triple. It
is a fine opening line, but say right away that the bad spots are local, so
one pass is enough.

One pass. Walk the string while tracking run, the length of the
current block of equal characters ending at i, and start, the left end
of the best valid window that ends at i.

  • If s[i] == s[i-1], run += 1; otherwise run = 1.
  • When run reaches 3, the window may not contain s[i-2..i] all
    together. The longest valid window ending at i therefore starts at
    i - 1 (it keeps the last two equal characters). Set start = i - 1
    and run = 2.
  • After each step the answer is max(best, i - start + 1).

Why it is correct. Invariant: s[start..i] is the longest valid
substring that ends at i. Moving start further right than needed would
only shorten the window, and any start left of i - 1 after a triple would
include s[i-2..i]. Every valid substring ends somewhere, so taking the max
over all i covers them all.

The same loop works for any alphabet: nothing depends on the characters
being a/b. It also generalizes to "no run longer than k" by swapping
the constant 3 for k + 1.

Code

from typing import Optional


def longest_semi_alternating(s: str, max_run: int = 2) -> int:
    """Length of the longest substring with no run of equal chars > max_run."""
    if max_run < 1:
        raise ValueError("max_run must be at least 1")
    n = len(s)
    if n <= max_run:
        return n

    best = 1
    start = 0  # left end of the longest valid window ending at i
    run = 1    # length of the equal-character run ending at i
    for i in range(1, n):
        run = run + 1 if s[i] == s[i - 1] else 1
        if run > max_run:
            # Keep only the last max_run copies of s[i].
            start = i - max_run + 1
            run = max_run
        best = max(best, i - start + 1)
    return best


def longest_semi_alternating_span(s: str, max_run: int = 2) -> Optional[tuple[int, int]]:
    """Follow-up: return (left, right) inclusive bounds of the first longest window."""
    if not s:
        return None
    best_len, best_span = 1, (0, 0)
    start, run = 0, 1
    for i in range(1, len(s)):
        run = run + 1 if s[i] == s[i - 1] else 1
        if run > max_run:
            start, run = i - max_run + 1, max_run
        if i - start + 1 > best_len:
            best_len, best_span = i - start + 1, (start, i)
    return best_span


if __name__ == "__main__":
    assert longest_semi_alternating("") == 0
    assert longest_semi_alternating("z") == 1
    assert longest_semi_alternating("zz") == 2
    assert longest_semi_alternating("zzz") == 2
    assert longest_semi_alternating("ccccc") == 2
    assert longest_semi_alternating("xyzxyz") == 6
    assert longest_semi_alternating("ppqqpp") == 6
    assert longest_semi_alternating("mmmnnm") == 5          # "mmnnm"
    assert longest_semi_alternating("ttxttt") == 5          # "ttxtt"
    assert longest_semi_alternating("kkkhhkkkhh") == 6      # "kkhhkk"
    assert longest_semi_alternating("abbbcddde") == 5       # "bbcdd"
    assert longest_semi_alternating("aaaa", max_run=1) == 1
    assert longest_semi_alternating("aabbaab", max_run=3) == 7
    assert longest_semi_alternating_span("mmmnnm") == (1, 5)
    assert longest_semi_alternating_span("") is None

    # Cross-check against brute force.
    import itertools
    import random

    def brute(t: str) -> int:
        best = 0
        for i in range(len(t)):
            for j in range(i, len(t)):
                sub = t[i:j + 1]
                if all(len(list(g)) <= 2 for _, g in itertools.groupby(sub)):
                    best = max(best, j - i + 1)
        return best

    rng = random.Random(7)
    for _ in range(2000):
        t = "".join(rng.choice("ab") for _ in range(rng.randint(0, 12)))
        assert longest_semi_alternating(t) == brute(t), t
    print("ok")

Complexity

  • Time: O(n), one pass with constant work per character.
  • Space: O(1) extra (the span variant also stores only two indices).
  • Brute force for comparison: O(n^2) with early stop, O(n^3) naive.

Test cases

  • "" -> 0 (empty input)
  • "z" -> 1; "zz" -> 2 (shorter than the limit, whole string)
  • "zzz" -> 2; "ccccc" -> 2 (one long run)
  • "xyzxyz" -> 6 (no repeats at all)
  • "ppqqpp" -> 6 (pairs only, whole string is valid)
  • "mmmnnm" -> 5 ("mmnnm", triple at the start)
  • "ttxttt" -> 5 ("ttxtt", triple at the end)
  • "kkkhhkkkhh" -> 6 ("kkhhkk", two triples split the string)
  • "abbbcddde" -> 5 ("bbcdd", window keeps two copies on each side)
  • max_run=1, "aaaa" -> 1; max_run=3, "aabbaab" -> 7
  • Large input: 10^5 copies of "a" -> 2, runs in linear time

Follow-ups

  1. Return the substring, not the length. Track the (start, i) pair
    when best improves (shown in longest_semi_alternating_span). Ask
    whether ties go to the first or last occurrence.
  2. No run longer than k. Replace 2 with k: when the run exceeds
    k, set start = i - k + 1. Same O(n) time and O(1) space.
  3. Count all valid substrings. The number of valid substrings ending
    at i is i - start + 1, so sum it instead of taking the max. Use a
    64-bit or Python int; the total is O(n^2).
  4. Allow up to m "bad" triples (or delete at most m characters).
    Use a general sliding window that counts violations inside it and
    advances the left pointer while the count exceeds m. Still O(n).
  5. Streaming input. The state is just (prev_char, run, current length, best), so it works on an unbounded stream with O(1) memory.
    A related version asks for the minimum deletions to make the whole
    string valid: delete run - 2 from each run, a single pass too.

Interviewer expectations

Mid-level (L4)

  • States the rule as "no run of three equal characters" and handles
    n < 3 and the empty string.
  • Gets to a correct O(n) pass, possibly after a brute force, with clean
    index handling.
  • Tests a triple at the start, middle, and end.

Senior (L5)

  • Goes straight to the one-pass window and explains the invariant (the
    window is the longest valid one ending at i) and why the new start is
    i - 1.
  • Generalizes to k and to counting substrings without rewriting.
  • Validates against a brute force on small random strings.

Staff (L6+)

  • Frames it as a sliding window with a local constraint and explains when
    the window can jump instead of shrinking one step at a time.
  • Handles the "allow m violations" and streaming variants and discusses
    Unicode or grapheme boundaries if the input is user text.
  • Keeps the code short, and talks through test strategy and edge cases
    without prompting.

Sign in to comment, vote or remix.