Show problems as
Classic problem #3MediumHash TableStringSliding Window

Longest Substring Without Repeating Characters

Real-world version: Largest Clean Tap Block
Tracked in this browser only
Read Longest Substring Without Repeating Characters on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstSliding Window · Strings, animated step by step

A lobby turnstile appends one character to a log string every time somebody taps a badge. That character is the person's short code, and codes are drawn from the full printable range: upper and lower case letters, digits, punctuation marks, and the space reserved for visitor passes. Codes are compared exactly, so K and k are two different people.

Security calls a block of back-to-back taps clean when no code shows up twice inside it. Given the log tape, return how many taps sit in the largest clean block. If nobody has tapped yet, report 0.

A block has to be an unbroken run of taps. You may not drop taps out of the middle of a block to keep it clean.

Examples

Example 1

Input
tape = "K7K7Q9"
Output
4

The last four taps K, 7, Q and 9 are all different codes. Any block of five taps here picks up a second 7.

Example 2

Input
tape = "PQQP"
Output
2

The trailing pair QP is clean. Stretching it one tap to the left gives QQP, which repeats Q, so 2 is the ceiling.

Example 3

Input
tape = "Q7! Q7!x"
Output
5

The visitor-pass space starts the winning block, which then runs Q, 7, ! and x for five distinct codes.

Constraints

  • 0 <= tape.length <= 10^5
  • Every character of `tape` is a printable code: an English letter, a digit, a punctuation symbol or a space
  • A space counts as a code like any other, so two spaces in one block make it unclean
  • Codes are case sensitive: an upper case letter and its lower case form are distinct codes

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def largest_clean_tap_block(tape: str) -> int:
Java
public int largestCleanTapBlock(String tape)

More on the same topics