Count same-color squares in a character grid
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are given a 2D grid (matrix) of characters. Each character represents a color: cells with the same character are considered the same color.
Formally:
- The grid has `m` rows and `n` columns.
- `grid[i][j]` is an alphabetic character (e.g., `'a'`–`'z'` or `'A'`–`'Z'`).
A **square** in this grid is defined as a contiguous `k × k` submatrix aligned with the grid axes, for some integer `k ≥ 1`.
A square is **monochromatic** if **all** of its cells contain the **same** character (i.e., the same color).
Task:
- Count and return the total number of monochromatic squares in the grid.
- Count all sizes of squares (1×1, 2×2, ..., up to the largest possible that fits in the grid).
Example (just for clarity, not necessarily exhaustive):
If the grid is:
```
a a b
a a b
b b b
```
Then some monochromatic squares include:
- All 1×1 cells (each single cell is a monochromatic square).
- The 2×2 square in the top-left corner formed by `'a'`.
Your function should return the total count of such monochromatic squares for a given input grid.
Quick Answer: This question evaluates understanding of 2D array manipulation, spatial pattern detection, and algorithmic counting with attention to time and space complexity.
You are given a 2D grid of characters, where each character represents a color. A square is a contiguous k × k submatrix aligned with the grid axes, for some k >= 1. A square is monochromatic if all of its cells contain the same character. Return the total number of monochromatic squares of all possible sizes and positions in the grid. Every 1 × 1 cell is considered a monochromatic square.
Constraints
- 0 <= len(grid) <= 1000
- If grid is non-empty, 0 <= len(grid[0]) <= 1000
- All rows in grid have the same length
- grid[i][j] is an alphabetic character
- The total number of cells is at most 1,000,000
Examples
Input: ([])
Expected Output: 0
Explanation: An empty grid contains no squares.
Input: (["aab", "aab", "bbb"])
Expected Output: 10
Explanation: There are 9 single-cell squares and one 2x2 monochromatic square of 'a' in the top-left corner.
Hints
- Try defining dp[i][j] as the side length of the largest monochromatic square whose bottom-right corner is cell (i, j).
- A square larger than 1 can end at (i, j) only if the current cell matches its top, left, and top-left neighboring cells.