//HashMap + Array solution: generate a signature for each row and put it in the hashmap; only check for signatures with freq N
//Time: O(m * n), 14ms
//Space: O(m * n)
class Solution {
    public int findBlackPixel(char[][] picture, int N) {
        int m = picture.length;
        if(m == 0) return 0;
        int n = picture[0].length;
        if(n == 0) return 0;

        Map<String, Integer> map = new HashMap<>();
        int[] colCount = new int[n];

        for(int i = 0; i < m; i++) {
            String s = countRow(picture, N, i, colCount);
            if(s.length() != 0) {
                map.put(s, map.getOrDefault(s, 0) + 1);
            }
        }

        int ans = 0;
        for(String s : map.keySet()) {
            if(map.get(s) == N) {//Check for rows that possibly contain the pixels we are looking for
                for(int i = 0; i < s.length(); i++) {
                    if(s.charAt(i) == 'B' && colCount[i] == N) {
                        ans += N;
                    }
                }
            }
        }
        return ans;
    }

    //Generate a signature for each row if there are N Bs in the row and put it in the map
    //Update the colCount
    private String countRow(char[][] picture, int N, int r, int[] colCount) {
        int count = 0;
        StringBuilder s = new StringBuilder();
        for(int i = 0; i < picture[0].length; i++) {
            if(picture[r][i] == 'B') {
                count++;
                colCount[i]++;
            }
            s.append(picture[r][i]);
        }
        if(count == N) {
            return s.toString();
        }
        return "";
    }
}