1072 - Flip Columns For Maximum Number of Equal Rows

You are given an m x n binary matrix matrix.

You can choose any number of columns in the matrix and flip every cell in that column (i.e., Change the value of the cell from 0 to 1 or vice versa).

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

 Example 1:

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

Example 2:

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

Example 3:

Input: matrix = [[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.

 Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] is either 0 or 1.

C++

• class Solution {
  public:
      int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
          unordered_map<string, int> cnt;
          int ans = 0;
          for (auto& row : matrix) {
              string s;
              for (int x : row) {
                  s.push_back('0' + (row[0] == 0 ? x : x ^ 1));
              }
              ans = max(ans, ++cnt[s]);
          }
          return ans;
      }
  };

JAVA

• class Solution {
      public int maxEqualRowsAfterFlips(int[][] matrix) {
          Map<String, Integer> cnt = new HashMap<>();
          int ans = 0, n = matrix[0].length;
          for (var row : matrix) {
              char[] cs = new char[n];
              for (int i = 0; i < n; ++i) {
                  cs[i] = (char) (row[0] ^ row[i]);
              }
              ans = Math.max(ans, cnt.merge(String.valueOf(cs), 1, Integer::sum));
          }
          return ans;
      }
  }

PYTHON

• from collections import defaultdict
  
  class Solution:
      def maxEqualRowsAfterFlips(self, matrix):
          cnt = defaultdict(int)
          ans = 0
          for row in matrix:
              s = ''.join('0' if row[0] == 0 else str(x ^ 1) for x in row)
              cnt[s] += 1
              ans = max(ans, cnt[s])
          return ans