A mosaic is a list of equal-length strings mosaic of lowercase letters; each letter is a tile colour. A panel is any rectangle of whole tiles (any height and width of at least 1, fully inside the mosaic). A panel is paired when every colour inside it appears an even number of times, so its tiles can be sold in matching pairs.
Return the number of paired panels.
Examples
Input: mosaic = ["aab", "bba"]
Output: 4
Explanation: "aa" in row 0, "bb" in row 1, the 2 x 2 block of columns 0-1
(a, a, b, b) and the 2 x 2 block of columns 1-2 (a, b, b, a).
Input: mosaic = ["ab", "ab"]
Output: 3
Explanation: each column, and the whole mosaic.
Input: mosaic = ["z"]
Output: 0
Constraints
1 <= rows <= 50,1 <= cols <= 400- Every character is a lowercase letter
a-z. - Target complexity: O(rows^2 * cols). Checking all O(rows^2 * cols^2) panels, even in O(1) each, is too slow for the largest tests.
Goals
- Record the odd/even state of 26 counts as one integer
- Collapse a band of rows into one list of column states
- Count equal prefix states along the band with a dictionary