Count OPTIVER in a Letter Grid Across Rows, Columns and Reversed Readings
Company: Optiver
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
Given a rectangular grid of uppercase English letters, count how many times the word `OPTIVER` appears when read along a straight line of consecutive cells in any of these four directions:
- left to right along a row;
- right to left along a row (the word appears reversed in that row);
- top to bottom along a column;
- bottom to top along a column (the word appears reversed in that column).
The grid is given as a list of strings: each string is one row, and all rows have the same length.
### Function Signature
```python
def count_optiver(grid: list[str]) -> int:
```
### Rules
- An occurrence is a run of 7 consecutive cells in one row or one column whose letters, read in one of the four directions above, spell `OPTIVER` exactly.
- Diagonal readings do not count, and a reading may not bend or wrap around the edge of the grid.
- Occurrences are counted independently. The same cell may be part of several occurrences, for example a horizontal one and a vertical one that share the letter `O`.
- An occurrence is identified by its starting cell (the cell holding `O`) and its direction. Because `OPTIVER` is not a palindrome, the same 7 cells can never match in both of their two opposite reading directions.
- Return the total number of occurrences, or `0` if there are none (in particular whenever the grid has fewer than 7 rows and fewer than 7 columns).
### Constraints
- `1 <= R <= 1000`, where `R = len(grid)`
- `1 <= C <= 1000`, where `C = len(grid[i])` for every row `i`
- Every character is an uppercase letter from `A` to `Z`.
- The answer is at most `4 * R * C` (at most 4,000,000), which fits in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: grid = ["OPTIVERXREVITPO"]
Output: 2
```
Columns 0 through 6 read `OPTIVER` left to right, and columns 14 down to 8 read `OPTIVER` right to left. The grid has a single row, so no vertical occurrence is possible.
**Example 2**
```text
Input: grid = [
"OPTIVER",
"PAAAAAA",
"TAAAAAA",
"IAAAAAA",
"VAAAAAA",
"EAAAAAA",
"RAAAAAA"
]
Output: 2
```
Row 0 read left to right and column 0 read top to bottom both spell `OPTIVER`. They share the `O` in the top-left cell and count as two occurrences. Reading row 0 right to left, or column 0 bottom to top, gives `REVITPO`, which does not count.
**Example 3**
```text
Input: grid = [
"OXXXXXX",
"XPXXXXX",
"XXTXXXX",
"XXXIXXX",
"XXXXVXX",
"XXXXXEX",
"XXXXXXR"
]
Output: 0
```
The word appears only along the main diagonal, which is not one of the four allowed directions.
Overview: Count how many times the word OPTIVER appears in a rectangular grid of uppercase letters, reading rows left to right or right to left and columns top to bottom or bottom to top. Tests careful grid traversal, direction handling, boundary checks and precise counting rules.
Given a rectangular grid of uppercase English letters, count how many times the word `OPTIVER` appears when read along a straight line of consecutive cells in any of these four directions:
- left to right along a row;
- right to left along a row (the word appears reversed in that row);
- top to bottom along a column;
- bottom to top along a column (the word appears reversed in that column).
The grid is given as a list of strings `grid`: each string is one row, and all rows have the same length. Implement `count_optiver(grid)` and return the total number of occurrences as an integer.
### Rules
- An occurrence is a run of 7 consecutive cells in one row or one column whose letters, read in one of the four directions above, spell `OPTIVER` exactly.
- Diagonal readings do not count, and a reading may not bend or wrap around the edge of the grid.
- Occurrences are counted independently. The same cell may be part of several occurrences, for example a horizontal one and a vertical one that share the letter `O`.
- An occurrence is identified by its starting cell (the cell holding `O`) and its direction. Because `OPTIVER` is not a palindrome, the same 7 cells can never match in both of their two opposite reading directions.
- Return the total number of occurrences, or `0` if there are none (in particular whenever the grid has fewer than 7 rows and fewer than 7 columns).
### Constraints
- `1 <= R <= 1000`, where `R = len(grid)`
- `1 <= C <= 1000`, where `C = len(grid[i])` for every row `i`
- Every character is an uppercase letter from `A` to `Z`.
- The answer is at most `4 * R * C` (at most 4,000,000), which fits in a 32-bit signed integer; it never exceeds 2^31 - 1, so `int` is a sufficient return type in Java and C++.
### Example 1
```text
Input: grid = ["OPTIVERXREVITPO"]
Output: 2
```
Columns 0 through 6 read `OPTIVER` left to right, and columns 14 down to 8 read `OPTIVER` right to left. The grid has a single row, so no vertical occurrence is possible.
### Example 2
```text
Input: grid = [
"OPTIVER",
"PAAAAAA",
"TAAAAAA",
"IAAAAAA",
"VAAAAAA",
"EAAAAAA",
"RAAAAAA"
]
Output: 2
```
Row 0 read left to right and column 0 read top to bottom both spell `OPTIVER`. They share the `O` in the top-left cell and count as two occurrences. Reading row 0 right to left, or column 0 bottom to top, gives `REVITPO`, which does not count.
Constraints
- 1 <= R <= 1000, where R = len(grid)
- 1 <= C <= 1000, where C = len(grid[i]) for every row i
- Every character is an uppercase letter from A to Z.
- The answer is at most 4 * R * C (at most 4,000,000), which fits in a 32-bit signed integer.
Examples
Input: (['OPTIVERXREVITPO'],)
Expected Output: 2
Explanation: Source Example 1: a single row holds one left-to-right occurrence (columns 0-6) and one right-to-left occurrence (columns 14 down to 8).
Input: (['OPTIVER', 'PAAAAAA', 'TAAAAAA', 'IAAAAAA', 'VAAAAAA', 'EAAAAAA', 'RAAAAAA'],)
Expected Output: 2
Explanation: Source Example 2: row 0 left to right and column 0 top to bottom share the O cell and count separately; their reverse readings spell REVITPO and do not count.
Hints
- Reading a row right to left and finding OPTIVER is the same as reading it left to right and finding the reversed word REVITPO; the same holds for columns read bottom to top.
- Every occurrence lies entirely within 7 consecutive cells of a single row or a single column, so it can never continue past the end of a row or column.
- OPTIVER is not a palindrome, so a given run of 7 cells can match in at most one of its two reading directions, while occurrences that merely share cells are still counted separately.