1263. Distinct Grid Tiles
A mosaic workshop lays out a rectangular wall of lowercase-letter tiles, described by the character matrix grid. A panel is any k x k block of neighbouring cells, and two panels are the same pattern when all their cells match letter for letter. Panels may overlap, and panels at different positions that show the same pattern count once.
Return the number of distinct k x k patterns that occur in grid.
Comparing every pair of panels cell by cell is far too slow for a 300 by 300 wall. Aim for O(rows * cols) time and space by hashing all panels with a two-dimensional rolling hash.
Example 1
- Input:
- grid = [["a","b","a"],["b","a","b"],["a","b","a"]]k = 2
- Output:
- 2
- Explanation:
The four 2 x 2 panels are [a b / b a], [b a / a b], [b a / a b] and [a b / b a], which form two distinct patterns, so the answer is 2.
Example 2
- Input:
- grid = [["a","a","a","a"],["a","a","a","a"],["a","a","a","a"],["a","a","a","a"]]k = 2
- Output:
- 1
- Explanation:
Every 2 x 2 panel is all a, so there is exactly 1 distinct pattern.
Example 3
- Input:
- grid = [["x","y","z"],["y","z","x"],["z","x","y"]]k = 1
- Output:
- 3
- Explanation:
With k = 1 every cell is a panel and the letters x, y, z are the distinct patterns, so the answer is 3.
Constraints
1 ≤ rows, cols ≤ 300
1 ≤ k ≤ min(rows, cols)
grid contains lowercase letters only.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,400 msC++ 600 msJava 1,200 msJavaScript 1,200 msTypeScript 1,200 ms
Expected complexity
- Time
- O(rows * cols)
- Space
- O(rows * cols)