Katkat
Back

Find the Longest Run of One Character

NetflixSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Tests linear scan and two-pointer/state-tracking techniques to find the maximum number of consecutive identical characters in an ASCII string using constant auxiliary space.

Problem Statement

Given an ASCII string s, find the length of the longest contiguous run of identical characters.

A contiguous run is a non-empty substring consisting of the same character repeated consecutively. Note that runs separated by other characters must be counted independently, not aggregated across the string.

Your solution should run in O(n) time and use O(1) auxiliary space.

Function Signature

def longest_run(s: str) -> int:
    pass

Input & Output Format

  • Input: A string s containing zero or more standard ASCII characters.
  • Output: An integer representing the length of the longest contiguous run of identical characters. If the string is empty, return 0.

Constraints

  • 0 <= len(s) <= 10^6
  • s consists of printable ASCII characters and whitespace.
  • Auxiliary space complexity must be O(1).

Examples

Example 1

Input: s = "aabbbccccdd"
Output: 4
Explanation: The runs are "aa" (2), "bbb" (3), "cccc" (4), and "dd" (2). The maximum length is 4.

Example 2

Input: s = "ababba"
Output: 2
Explanation: Even though 'a' appears 3 times in total, the longest contiguous run of 'a' is "aa" (length 2). The answer is 2.

Example 3

Input: s = ""
Output: 0
Explanation: An empty string contains no runs, so the result is 0.

Edge Cases to Consider

  • Empty string s = ""
  • Single-character string s = "x"
  • String where all characters are identical s = "aaaa"
  • String with no consecutive identical characters s = "abcdef" (returns 1)
  • Whitespace runs (e.g., consecutive spaces or tabs)

Hints

Hint 1

Handle the empty string as a base case before initializing variables for tracking run lengths.

Hint 2

Maintain two integer variables: one for the current run length and one for the maximum run length seen so far.

Hint 3

Whenever the current character differs from the previous character, compare the current run length with your maximum and reset the counter to 1.

Follow-up questions

  • How would you modify the function to return both the character and the start index of the longest run?
  • If the input string is streamed as an infinite or chunked byte stream instead of loaded entirely in memory, how would you adapt your implementation?
  • How would you solve the problem if you are allowed to change at most k characters to maximize the longest consecutive run of a single character?