Flip Columns For Maximum Number of Equal Rows

Given a matrix consisting of 0s and 1s, we may choose any number of columns in the matrix and flip every cell in that column. Flipping a cell changes the value of that cell from 0 to 1 or from 1 to 0.

Return the maximum number of rows that have all values equal after some number of flips.

Example 1:

Input: [[0,1],[1,1]]
Output: 1
Explanation: After flipping no values, 1 row has all values equal.

Example 2:

Input: [[0,1],[1,0]]
Output: 2
Explanation: After flipping values in the first column, both rows have equal values.

Example 3:

Input: [[0,0,0],[0,0,1],[1,1,0]]
Output: 2
Explanation: After flipping values in the first two columns, the last two rows have equal values.

Note:

1. 1 <= matrix.length <= 300

2. 1 <= matrix[i].length <= 300

3. All matrix[i].length's are equal

4. matrix[i][j] is 0 or 1

class Solution {
    public int maxEqualRowsAfterFlips(int[][] matrix) {
        // We can make a single row into full 1s OR 0s
        if (matrix.length == 1)
            return 1;
        Map<String, Integer> map = new HashMap<>();
        int max = 0;
        // Observation -> 2 rows which are opposite of each other will become full on
        // same column flips
        for (int i = 0; i < matrix.length; i++) {
            StringBuilder str1 = new StringBuilder();
            StringBuilder str2 = new StringBuilder();
            for (int j = 0; j < matrix[i].length; j++) {
                str1.append(1 - matrix[i][j]);
                str2.append(matrix[i][j]);
            }
            String key1 = str1.toString(), key2 = str2.toString();
            map.put(key1, map.getOrDefault(key1, 0) + 1);
            max = Math.max(max, map.get(key1));
            map.put(key2, map.getOrDefault(key2, 0) + 1);
            max = Math.max(max, map.get(key2));
        }
        return max;
    }
}