Find the Longest Run of One Character
Company: Netflix
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Find the Longest Run of One Character
### Problem
Implement `longestIdenticalRun(text) -> length`.
Return the maximum number of consecutive positions containing the same character. A run must occupy adjacent positions; the same character appearing again after a different character starts a new run.
### Portable Contract
- `text` is an ASCII string, so each character has the same representation in Python, JavaScript, Java, and C++.
- `0 <= text.length <= 200,000` ASCII characters.
- Character comparison is exact and case-sensitive.
- An empty string returns `0`.
- The input must not be modified.
- Use `O(text.length)` time and `O(1)` auxiliary space.
```hint Track the current run
At each position, decide whether the current run extends or restarts, then compare its length with the best length seen so far.
```
### Examples
```text
text = "aaabbccccdaa"
length = 4
```
```text
text = "AbBB"
length = 2
```
```text
text = ""
length = 0
```
### Discussion Requirements
- Explain how the initialization avoids special-case errors for a one-character string.
- Identify tests for a run at the beginning, a run at the end, all-equal input, and all-distinct input.
- Explain why grouping counts across non-adjacent occurrences would solve a different problem.
Quick Answer: Implement the length of the longest consecutive run of one character in an ASCII string. Distinguish adjacent runs from total frequency while handling empty input, boundary transitions, linear scaling, and constant auxiliary state.
Implement `longestIdenticalRun(text) -> length`.
A **run** is a maximal block of adjacent positions in `text` that all hold the
same character. Return the length of the longest such run. Positions must be
adjacent: the same character appearing again after a different character starts
a brand-new run and does not extend the earlier one.
### Output semantics
- Return a single integer: the number of characters in the longest run.
- The answer is a length, never a position, so ties between two equally long
runs do not change the result.
- Character comparison is exact and case-sensitive: `'b'` and `'B'` are
different characters.
- An empty string returns `0`.
- `text` must not be modified.
### Examples
Example 1:
```text
text = "aaabbccccdaa"
length = 4
```
The runs are `aaa` (3), `bb` (2), `cccc` (4), `d` (1) and `aa` (2). The longest
is `cccc`, so the answer is `4`.
Example 2:
```text
text = "AbBB"
length = 2
```
Comparison is case-sensitive, so `'b'` and `'B'` do not form one run. The runs
are `A` (1), `b` (1) and `BB` (2), so the answer is `2`.
Example 3:
```text
text = "aabaa"
length = 2
```
The character `'a'` appears four times in total, but never more than twice in a
row, so the answer is `2` rather than `4`.
Constraints
- 0 <= text.length <= 200,000
- text contains ASCII characters only, so each character has the same representation in Python, JavaScript, Java, and C++
- Character comparison is exact and case-sensitive
- An empty string returns 0
- The input must not be modified
- 0 <= answer <= 200,000, so the result always fits in a 32-bit signed integer (int in Java, int in C++)
- Target complexity: O(text.length) time and O(1) auxiliary space
Examples
Input: ('',)
Expected Output: 0
Input: ('a',)
Expected Output: 1
Hints
- Every run ends at some position. If you know the length of the run that ends at each position, the answer is just the largest of those lengths.
- Compare each character with the one immediately before it to decide whether the run in progress continues or a new one begins.
- Pick the starting values of your counters so that a length-0 and a length-1 string fall out of the same loop with no special case, and remember that the longest run may be the one still open when the string ends.