Find the Longest Straight Run of One Color
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
Given a rectangular grid of colors, return the length of the longest consecutive sequence of cells with the same color along a horizontal, vertical, or diagonal straight line.
A sequence cannot change direction or skip a cell. Both diagonal orientations count. The length is the number of cells in the sequence.
### Input
- `grid`: an array of strings of equal length. Each character represents one cell's color.
### Output
Return the maximum length as an integer.
### Constraints and Edge Cases
- For this practice version, the grid contains at least one row and one column, with at most `1000000` cells in total.
- Colors are uppercase English letters; equal letters mean equal colors.
- A one-cell grid has answer `1`.
- Diagonal lines may run down-right or down-left. Reading the same line in reverse does not change its length.
- A connected region that bends is not necessarily one valid sequence.
### Example 1
```text
grid = ["RRRG", "RRBB", "GRRR", "BGBR"]
output = 4
```
The main diagonal contains four consecutive `R` cells.
### Example 2
```text
grid = ["RBG", "BGR", "GRB"]
output = 3
```
The down-left diagonal from the top-right cell contains three `G` cells. No horizontal or vertical sequence has that length.
Overview: Find the longest straight run of equal-colored cells across horizontal, vertical, and both diagonal directions in a rectangular grid.
Given a rectangular grid of colors, return the length of the longest consecutive sequence of cells with the same color along a horizontal, vertical, or diagonal straight line.
A sequence cannot change direction or skip a cell. Both diagonal orientations count. The length is the number of cells in the sequence.
### Input
- `grid`: an array of strings of equal length. Each character represents one cell's color.
### Output
Return the maximum length as an integer.
### Constraints and Edge Cases
- For this practice version, the grid contains at least one row and one column, with at most `1000000` cells in total.
- Colors are uppercase English letters; equal letters mean equal colors.
- A one-cell grid has answer `1`.
- Diagonal lines may run down-right or down-left. Reading the same line in reverse does not change its length.
- A connected region that bends is not necessarily one valid sequence.
### Example 1
```text
grid = ["RRRG", "RRBB", "GRRR", "BGBR"]
output = 4
```
The main diagonal contains four consecutive `R` cells.
### Example 2
```text
grid = ["RBG", "BGR", "GRB"]
output = 3
```
The down-left diagonal from the top-right cell contains three `G` cells. No horizontal or vertical sequence has that length.
Constraints
- grid is a nonempty list of equally long nonempty strings.
- The total number of cells is at most 1000000; no smaller independent dimension cap is imposed.
- Every cell is an uppercase English letter A through Z.
- Count only consecutive equal-color cells along one horizontal, vertical, down-right or down-left line; do not turn, skip or wrap.
Examples
Input: (['RRRG', 'RRBB', 'GRRR', 'BGBR'],)
Expected Output: 4
Explanation: Published sample 1: the main diagonal consists of four R cells.
Input: (['RBG', 'BGR', 'GRB'],)
Expected Output: 3
Explanation: Published sample 2: three G cells form the down-left diagonal.