Leetcode 1072: Flip Columns For Maximum Number of Equal Rows

https://leetcode.com/problems/flip-columns-for-maximum-number-of-equal-rows/description/

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

Notes:

The key to this question is to understand the key logic here.

One way is that we can start with a smaller size. Let say we only have two  rows only. Then how can we reach the maximum?

There are only two cases that we can reach 2, otherwise it is 1.

One is that these two arrays are valid by themselves, so we do not need any flip;

The other is that every elements of the two arrays are just opposite.

After figuring out this, this question is asking for the maximum number of "similar" rows: either the same or just opposite on every column.

See the code below:

class Solution {

public:

    int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {

        int res = 0;

      //  if(!matrix.size() || !matrix.front().size()) return res;

        int m = matrix.size(), n = matrix.front().size();

       // vector<int> used(m, 0);

        unordered_map<string, int> mp;

        for(auto &a : matrix) {

            string s1, s2;

            for(auto &b : a) {

                s1.push_back(b+'0');

                s2.push_back(1-b+'0');

            }

            ++mp[s1];

            ++mp[s2];

            res = max(res, max(mp[s1], mp[s2]));

         }

        return res;

    }

};