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 <= matrix.length <= 300
1 <= matrix[i].length <= 300
All matrix[i].length's are equal
matrix[i][j] is 0 or 1

Difficulty: interview

Starter code:

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        

Solutions:
class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        dict_ = {}
        for row in matrix:
            curr_tuple = tuple(row)
            dict_[curr_tuple] = 1 + dict_.get(curr_tuple,0)
        visited = set()
        max_same = 0
        for row in matrix:
            curr_tuple = tuple(row)
            if curr_tuple in visited:
                continue
            visited.add(curr_tuple)
            inverse = [1] * len(row)
            for i in range (len(row)):
                if row[i]:
                    inverse[i] = 0
            curr_inv = tuple(inverse)
            visited.add(curr_inv)
            curr_sum = 0
            curr_sum = dict_[curr_tuple]
            if curr_inv in dict_:
                curr_sum += dict_[curr_inv]
            if curr_sum > max_same:
                max_same = curr_sum
        return max_same


class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        pattern_dict = {}
        for row in matrix:
            if row[0] == 0:
                key = tuple(row)
            else:
                newrow = [1-x for x in row]
                key = tuple(newrow)
            if key in pattern_dict:
                pattern_dict[key] += 1
            else:
                pattern_dict[key] = 1
        maxnum = 0
        for _, num in pattern_dict.items():
            maxnum = max(maxnum, num)
        return maxnum

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        ## row by row store bit sequence
        ## row by row store sequence that is xor of it (xor with all 1s)
        ## hash map to track
        
        if len(matrix) == 0: 
            return 0
        
        cols = len(matrix[0])
        allOnes = 0
        for i in range(0, cols): 
            allOnes <<= 1
            allOnes |= 1
        
        freq = {}
        count = 0
        for i in range(0, len(matrix)): 
            
            rowNumber = 0
            for j in range(0, len(matrix[i])): 
                rowNumber = rowNumber<<1
                rowNumber = rowNumber|matrix[i][j]
                

            xorRowNumber = rowNumber^allOnes
            
            if rowNumber in freq:
                freq[rowNumber] += 1
                count = max(count, freq[rowNumber])
            elif xorRowNumber in freq:
                freq[xorRowNumber] += 1
                count = max(count, freq[xorRowNumber])
            else:
                freq[rowNumber] = 1
                count = max(count, freq[rowNumber])
                
        return count
                


class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
#         iMax = len(matrix)
#         jMax = matrix[0]
#         flipCounter = [0 for _ in range(jMax)]
        
        
        counterDict = defaultdict(int)
        for row in matrix:
            str0 = \"\"
            str1 = \"\"
            for num in row:
                str0 += str(num)
                str1 += str(abs(num-1))
            counterDict[str0] += 1
            counterDict[str1] += 1
        return max(counterDict.values())

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        dic={}
        for i in range(len(matrix)):
            a=''
            b=''
            for j in range(len(matrix[0])):
                a=a+'%d'%matrix[i][j]
                b=b+'%d'%(1-matrix[i][j])
       #     print(a,b,dic)
            if a not in dic:
                dic[a]=1
            else:
                dic[a]+=1
            if b not in dic:
                dic[b]=1
            else:
                dic[b]+=1
        m=0
        #print(dic)
        for k in dic.keys():
            m=max(m,dic[k])
        return m

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        counter = {}
        for row in matrix:
            key = tuple(x^row[0] for x in row)
            counter[key] = counter.get(key, 0)+1
        return max(counter.values())

import collections
class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        # return max(collections.Counter(tuple(x ^ r[0] for x in r) for r in matrix).values())
        values = {}
        for row in matrix:
            s1, s2 = '', ''
            for c in row:
                s1 += str(c ^ 0)
                s2 += str(c ^ 1)
            print((s1, s2))
            if values.get(s1, 0):
                values[s1] += 1
            elif values.get(s2, 0):
                values[s2] += 1
            else:
                values[s1] = 1
        return max(values.values())


class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        values = {}
        for row in matrix:
            s1, s2 = '', ''
            for c in row:
                s1 += str(c ^ 0)
                s2 += str(c ^ 1)
            print((s1, s2))
            if values.get(s1, 0):
                values[s1] += 1
            elif values.get(s2, 0):
                values[s2] += 1
            else:
                values[s1] = 1
        return max(values.values())


class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
      dicts = {}
      for row in matrix:
        bin_rep = ''.join([str(x) for x in row])
        if bin_rep not in dicts: dicts[bin_rep] = 1
        else: dicts[bin_rep] += 1
        rev_bin_rep = ''.join([str(x^1) for x in row])
        if rev_bin_rep not in dicts: dicts[rev_bin_rep] = 1
        else: dicts[rev_bin_rep] += 1
        #print (bin_rep, rev_bin_rep)
      res = 0
      #print (dicts)
      for key,value in dicts.items():
        res = max(res, value)
      return res

class Solution:
    def maxEqualRowsAfterFlips(self, ma: List[List[int]]) -> int:
        n=len(ma)
        m=len(ma[0])
        di={}
        for i in range(n):
            s=''
            ss=''
            for j in range(m):
                s=s+str(ma[i][j])
                ss=ss+str(1-ma[i][j])
            di[s]=di.get(s,0)+1
            di[ss]=di.get(ss,0)+1
        return max(list(di.values()))

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        values = {}
        for row in matrix:
            s1, s2 = '', ''
            for c in row:
                s1 += str(c ^ 0)
                s2 += str(c ^ 1)
            print((s1, s2))
            values[s1] = values.get(s1, 0) + 1
            values[s2] = values.get(s2, 0) + 1
        return max(values.values())


import collections
class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        return max(collections.Counter(tuple(x ^ r[0] for x in r) for r in matrix).values())
        # values = {}
        # for row in matrix:
        #     s1, s2 = '', ''
        #     for c in row:
        #         s1 += str(c ^ 0)
        #         s2 += str(c ^ 1)
        #     print(s1, s2)
        #     if values.get(s1, 0):
        #         values[s1] += 1
        #     elif values.get(s2, 0):
        #         values[s2] += 1
        #     else:
        #         values[s1] = 1
        # return max(values.values())


class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        def find_minor(row):
            one = row.count(1)
            if one * 2 == len(row):
                return tuple(i for i, val in enumerate(row) if val == row[-1])
            elif one * 2 > len(row):
                return tuple(i for i, val in enumerate(row) if val == 0)
            return tuple(i for i, val in enumerate(row) if val == 1)
        counts = collections.Counter()

        for i, row in enumerate(matrix):
            counts[find_minor(row)] += 1
        return max(counts.values())

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        n=len(matrix)
        m=len(matrix[0])
        mx=1
        for i in range(n):
            c=[0 for i in range(m)]
            for j in range(m):
                if(matrix[i][j]==0):
                    c[j]=1
                else:
                    c[j]=0
            count=1
            for j in range(n):
                if(i!=j)and(c==matrix[j])or(matrix[i]==matrix[j]):
                    count+=1
            mx=max(mx,count)
        return mx-1


class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        
        n = len(matrix)
        m = len(matrix[0])
        res = 0
        for i in range(n):
            flip = [1-matrix[i][j] for j in range(m) ]
            
            cnt = 0
            for k in range(n):
                if matrix[i] == matrix[k] or flip ==  matrix[k]:
                    cnt += 1
                    
            res = max(res, cnt)
        
        return res


class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        
        counter = collections.Counter()
        
        for row in matrix:
            flipper = {1: 0, 0: 1}
            
            if row[0] == 0:
                row = [flipper[col] for col in row]
            
            counter[tuple(row)] += 1
            
        return max(counter.values())

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        hashmap = {}
        for i in range(m):
            order = \"\"
            first = matrix[i][0]
            
            for j in range(1, n):
                if matrix[i][j] == first:
                    order += \"1\"
                
                else:
                    order += \"0\"
            
            hashmap[order] = hashmap.get(order, 0) + 1
        
        return max(hashmap.values())

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        rows = {}
        max_value = 0
        n = len(matrix)
        m = len(matrix[0])
        for i in range(n):
            a = []
            b = []
            for j in range(m):
                if matrix[i][j]==0:
                    a.append(j)
                else:
                    b.append(j)
            a = tuple(a)
            b = tuple(b)
            if a not in rows:
                rows[a] = 0
            if b not in rows:
                rows[b] = 0
            rows[a]+=1
            rows[b]+=1
            max_value = max(max_value, rows[a], rows[b])
        return max_value
                    


class Solution:
    def maxEqualRowsAfterFlips(self, mat: List[List[int]]) -> int:
        
        dic = defaultdict(lambda : 0)
        for r in range(len(mat)):
            row = mat[r]
            ones = 0
            zeros = 0
            for i in range(len(row)):
                if row[i] == 0:
                    ones = ones<<1
                    zeros = zeros<<1
                    ones |= 1
                else:
                    zeros = zeros<<1
                    ones = ones<<1
                    zeros |= 1
            dic[zeros] += 1
            dic[ones] += 1
        return max(dic.values()) 

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        cache = collections.defaultdict(int)
        for row in matrix:
            vals = []
            trans = []
            for c in row:
                vals.append(c)
                trans.append(1 - c)
            cache[str(vals)] += 1
            cache[str(trans)] += 1
        return max(cache.values())

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        rows = {}
        max_value = 0
        n = len(matrix)
        for i in range(n):
            if matrix[i][0]==1:
                a = tuple(matrix[i])
            else:
                a = tuple([1-c for c in matrix[i]])
           # for j in range(m):
          #      if matrix[i]  # [j]==0:
              #      a+=str(j)
           #     else:
          #          b+=str(j)
            #a = tuple(a)
            #b = tuple(b)
            if a not in rows:
                rows[a] = 0
           # if b not in rows:
         #       rows[b] = 0
            rows[a]+=1
         
        # rows[b]+=1
            max_value = max(max_value, rows[a])
        return max_value
                    


class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        rows = {}
        max_value = 0
        n = len(matrix)
        for i in range(n):
            if matrix[i][0]==0:
                a = tuple(matrix[i])
            else:
                a = tuple([1-c for c in matrix[i]])
           # for j in range(m):
          #      if matrix[i]  # [j]==0:
              #      a+=str(j)
           #     else:
          #          b+=str(j)
            #a = tuple(a)
            #b = tuple(b)
            if a not in rows:
                rows[a] = 0
           # if b not in rows:
         #       rows[b] = 0
            rows[a]+=1
         
        # rows[b]+=1
            max_value = max(max_value, rows[a])
        return max_value
                    


from collections import Counter

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        c = Counter()
        for row in matrix:
            c.update([tuple(row)])
            c.update([tuple(flip(row))])
        return max(c.values())

def flip(bits):
    return [1 if bit == 0 else 0 for bit in bits]

import collections
class Solution:
    def maxEqualRowsAfterFlips(self, A) -> int:
        return max(collections.Counter(tuple(x ^ r[0] for x in r) for r in A).values())

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        
        res = 0
        n, m = len(matrix), len(matrix[0])
        
        for i in range(n):
            count = 0
            flip = [0 for _ in range(m)]
            
            for j in range(m):
                flip[j] = 1 - matrix[i][j]
            
            for k in range(i, n):
                if matrix[k] == matrix[i] or matrix[k] == flip:
                    count += 1
            
            res = max(res, count)
        
        return res

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        f=defaultdict(int)
        n=len(matrix[0])
        for i in matrix:
            p,q=[],[]
            for j in range(n):
                if i[j]==0:p.append(j)
                else:q.append(j)
            f[tuple(p)]+=1
            f[tuple(q)]+=1
        return max(f.values())

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        map = collections.defaultdict(int)
        for row in matrix:
            map[\"\".join([str(j) for j in row])] += 1
            map[\"\".join([str(1-j) for j in row])] += 1
        return max(map.values())

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        for i,row in enumerate(matrix):
            matrix[i]=tuple(x^row[0] for x in row)
        return max(Counter(matrix).values())


class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        cntMap = {}
        flipper = {1: 0, 0: 1}
        max_val = 0
        for row in matrix:
            r, tran = \"\", \"\"
            for k in row:
                r += str(k)
                tran += str(flipper[k])
            key = r
            cntMap.setdefault(r, 0)
            cntMap.setdefault(tran, 0)
            cntMap[r] += 1
            cntMap[tran] += 1
            max_val = max(max_val, cntMap[r])
            max_val = max(max_val, cntMap[tran])

        return max_val
                
        

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        rows = {}
        max_value = 0
        n = len(matrix)
        m = len(matrix[0])
        for i in range(n):
            a = ''
            b = ''
            for j in range(m):
                if matrix[i][j]==0:
                    a+=str(j)
                else:
                    b+=str(j)
            #a = tuple(a)
            #b = tuple(b)
            if a not in rows:
                rows[a] = 0
            if b not in rows:
                rows[b] = 0
            rows[a]+=1
            rows[b]+=1
            max_value = max(max_value, rows[a], rows[b])
        return max_value
                    


class Solution:
    def maxEqualRowsAfterFlips(self, x: List[List[int]]) -> int:
        f=defaultdict(int)
        n=len(x[0])
        for i in x:
            p=q=0
            v=1
            for j in range(n):
                if i[j]==0:p|=v
                else:q|=v
                v=v<<1
            f[p]+=1
            f[q]+=1
        return max(f.values())

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        noninv = {}
        
        for row in matrix:
            row = repr(row)
            if row in noninv:
                noninv[row] += 1
            else:
                noninv[row] = 1
            
        count = 0
        for row in matrix:
            revrow = [i^1 for i in row]
            revrow = repr(revrow)
            row = repr(row)
            
            if revrow in noninv:
                count = max(count, noninv[row] + noninv[revrow])
            else:
                count = max(count, noninv[row])
            
        return count
        


class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        counter = collections.Counter()
        flipper = {1: 0, 0: 1}
        
        for row in matrix:
            if row[0] == 0:
                row = [flipper[col] for col in row]
                
            counter[tuple(row)] += 1
            
        return max(counter.values())

from collections import defaultdict
class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        '''
        # Analysis:
            
        
        '''
        lookup = collections.defaultdict(int)
        for row in matrix:
            vals = []
            trans = []
            for c in row:
                vals.append(c)
                trans.append(1 - c)
            lookup[str(vals)] += 1
            lookup[str(trans)] += 1
        return max(lookup.values())

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        dict_ = {}
        for row in matrix:
            curr_tuple = tuple(row)
            dict_[curr_tuple] = 1 + dict_.get(curr_tuple,0)
        
        max_same = 0
        for row in matrix:
            curr_tuple = tuple(row)
            inverse = [1] * len(row)
            for i in range (len(row)):
                if row[i]:
                    inverse[i] = 0
            curr_inv = tuple(inverse)
            curr_sum = 0
            curr_sum = dict_[curr_tuple]
            if curr_inv in dict_:
                curr_sum += dict_[curr_inv]
            if curr_sum > max_same:
                max_same = curr_sum
        return max_same


class Solution:
    def maxEqualRowsAfterFlips(self, mat: List[List[int]]) -> int:
        ans = 0
        m, n = len(mat), len(mat[0])
        ones = [[0]*n for i in range(m)]
        zeros = [[0]*n for i in range(m)]
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 1:
                    zeros[i][j] = 1
                else:
                    ones[i][j] = 1

        for i in range(m):
            for target in [ones[i], zeros[i]]:
                count = 1
                for k in range(m):
                    if k == i: continue
                    if ones[k] == target or zeros[k] == target:
                        count += 1
                ans = max(ans, count)
        return ans 

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        d = {}
        for arr in matrix:
            if arr[0] == 0:
                k = \"\".join(str(a) for a in arr)
            else:
                k = \"\".join(\"1\" if a==0 else \"0\" for a in arr)
            if k in d:
                d[k] += 1
            else:
                d[k] = 1
        return max(d.values())

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        def reverse_row(row):
            res = [0] * len(row)
            for i, val in enumerate(row):
                res[i] = 1 - row[i]
            return res
                
        d = {}
        for row in matrix:
            rev_row = reverse_row(row)

            if tuple(row) in d:
                d[tuple(row)] += 1
            elif tuple(rev_row) in d:
                d[tuple(rev_row)] += 1
            else:
                d[tuple(row)] = 1

        res = sorted(d.items(), key=lambda x: x[1], reverse=1)
        return res[0][1]

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        counter = collections.defaultdict(int)
        
        for row in matrix:
            if row[0] == 1:
                row = [1 - num for num in row]
            counter[tuple(row)] += 1
        
        return max(counter.values())


#https://www.cnblogs.com/seyjs/p/11026157.html

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        memo = collections.defaultdict(lambda : 0)
        for line in matrix:
            if line[0]==0:
                memo[tuple(line)] += 1
            else:
                line = [1 if i==0 else 0 for i in line]
                memo[tuple(line)] += 1
        return max(memo.values())


class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        def flip(row):
            return [1-r for r in row]
        
        record=dict()
        for row in matrix:
            record[tuple(row)]=record.get(tuple(row),0)+1
            record[tuple(flip(row))]=record.get(tuple(flip(row)),0)+1
        return max(record.values())

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        groups = {}
        for row in matrix:
            tuple_row = tuple(row)
            if tuple_row not in groups:
                groups[tuple_row] = 1
            else:
                groups[tuple_row] += 1
        max_equal = 0
        for row in groups.keys():
            rev_row = tuple([1-x for x in row])
            group_max = groups[row]
            if row != rev_row and rev_row in groups:
                group_max += groups[rev_row]
            max_equal = max(max_equal, group_max)
            
        return max_equal

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        columnsToFlipOneForEqualRow = {}
        columnsToFlipZeroForEqualRow = {}
        self.height = len(matrix)
        self.width = len(matrix[0])
        
        for y in range(self.height):
            row = matrix[y]
            columnsToFlipOneForEqualRow[y] = []
            columnsToFlipZeroForEqualRow[y] = []
            
            for x in range(self.width):
                element = row[x]
                
                if element == 0:
                    columnsToFlipOneForEqualRow[y].append(x)
                else:
                    columnsToFlipZeroForEqualRow[y].append(x)
                    
        patterns = {}
        
        for index in range(self.height):
            first = str(columnsToFlipOneForEqualRow[index])
            second = str(columnsToFlipZeroForEqualRow[index])
            
            if first not in patterns:
                patterns[first] = 0
                
            if second not in patterns:
                patterns[second] = 0
                
            patterns[first] += 1
            patterns[second] += 1
            
        return max(patterns.values())


class Solution:
    def convert_to_tuple(self, lst):
        if lst[0] == 0:
            return tuple(lst)
        else:
            return tuple([int(not x) for x in lst])
    
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        from collections import defaultdict
        row_counts = defaultdict(int)
        
        for row in matrix:
            row_counts[self.convert_to_tuple(row)] += 1
            
        return max(row_counts.values())
        
        


import collections
class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        ans = 1
        orig = collections.defaultdict(int)
        orig_to_xor = {}
        for row in matrix:
            curr_orig = 0
            curr_xor = 0
            for i, c in enumerate(row):
                curr_orig ^= c<<i
                curr_xor ^= (1-c)<<i
            orig[curr_orig] += 1
            orig_to_xor[curr_orig] = curr_xor
        for curr_orig, curr_xor in orig_to_xor.items():
            ans = max(orig[curr_orig] + orig[curr_xor], ans) if curr_orig!=curr_xor else max(orig[curr_orig], ans)
        return ans

from math import floor
from math import ceil
from math import sqrt
from collections import deque
import numpy
from _collections import deque
#from _ast import Num # LC doesn't like this
from heapq import *
from typing import List
import random

MOD = int(1e9 + 7)
BASE = 256


class Solution:

    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        N = len(matrix)
        M = len(matrix[0])
        sigCnt = {}
        for i in range(N):
            if matrix[i][0]:
                for c in range(M):
                    matrix[i][c] = 1 - matrix[i][c]
            sig = \"\".join(map(str, matrix[i]))
            if not sig in sigCnt:
                sigCnt[sig] = 0
            sigCnt[sig] += 1
        return max(sigCnt.values())

\"\"\"
s = Solution()
l = [[0, 1], [1, 1]]
l = [[0, 1], [1, 0]]
l = [[0, 0, 0], [0, 0, 1], [1, 1, 0]]
print(s.maxEqualRowsAfterFlips(l))
\"\"\"


from collections import Counter
class Solution:
    def maxEqualRowsAfterFlips(self, matrix):
        counter = Counter()
        flip = {1: 0, 0: 1}
        
        for row in matrix:
            if row[0] == 0 :
                row = [flip[col] for col in row]
                
            counter[tuple(row)] += 1
            
        return max(counter.values())

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        seen = defaultdict(int)
        
        for row in matrix:
            comp = row[0] == 1
            
            temp = []
            
            for num in row:
                if comp:
                    temp.append(str(num ^ 1))
                else:
                    temp.append(str(num))
            
            seen[''.join(temp)] += 1
    
        return max(seen.values())

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        for i in range(m):
            if matrix[i][0] == 1:
                for j in range(n):
                    matrix[i][j] ^= 1
        cnt = Counter(list(map(tuple, matrix)))
        return max(cnt.values())


class Solution:
    def maxEqualRowsAfterFlips(self, mat: List[List[int]]) -> int:
        
        
        s=collections.defaultdict(lambda: 0)
        m=len(mat)
        n=len(mat[0])
        st=\"\"
        maxi=0
        for i in range(m):
            for j in range(n-1):
                if(mat[i][j]==mat[i][j+1]):
                    st+='1'
                else: 
                    st+='0'
            s[st]+=1
            maxi=max(maxi, s[st])
            st=\"\"
        return maxi
        
        
    

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        memo = collections.defaultdict(lambda : 0)
        M = len(matrix)
        N = len(matrix[0])
        for line in matrix:
            if line[0]==0:
                memo[tuple(line)] += 1
            else:
                line = [1 if i==0 else 0 for i in line]
                memo[tuple(line)] += 1
        return max(memo.values())
            
#         print (dict(memo))
#         # return 0
#         res = 0
#         for key, val in memo.items():
#             res = max(res, val)
#             # if key[0]==0 or key[1]==0 or key[0]==key[1]:
#             #     res = max(res, val)
#             if key[0]!=key[1] and (key[1], key[0]) in memo and  memo[(key[1], key[0])]!=0:
#                 res = max(res, memo[key]+memo[(key[1], key[0])])
#             # else:
#             #     res = max(res, val)
#         return res


class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        '''
        Find the maxmimum number of rows in rows[]
        where rows[i] = rows[i+1]
        '''
        ans = 0
        for i, r in enumerate(matrix):
            count = 0
            flip = [1-x for x in r]
            for j in range(i, len(matrix)):
                if r == matrix[j] or flip == matrix[j]:
                    count += 1
            ans = max(ans, count)
        return ans
            



class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        cache = collections.defaultdict(int)
        for row in matrix:
            vals = []
            trans = []
            for c in row:
                vals.append(c)
                trans.append(1 - c)
            cache[str(vals)] += 1
            cache[str(trans)] += 1
        return max(cache.values())


class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        return max(Counter(tuple(num^r[0] for num in r) for r in matrix).values())


class Solution:
    def maxEqualRowsAfterFlips(self, g: List[List[int]]) -> int:
        # want to find number of rows that are identical or exactly opposite
        # i.e. after flipping cols these can be all 1's or all 0's

        # pass 1: iterate grid rows
        # store vectors in dict hashmap {vector : freq}
        # remember that dict keys must be immutable, hence tuple

        # pass 2: iterate dict keys
        # create inverse (XOR), check frequency of exact match + inverse
        # take the max over all rows, return
        # O(M + MN) time, O(M) space

        rows, cols, d = len(g), len(g[0]), {}
        for row in range(rows):
            vct = tuple(g[row])
            d[vct] = d.setdefault(vct, 0) + 1

        res = 0
        for vct in d:
            inv = tuple(el ^ 1 for el in vct)

            if inv in d: matches = d[vct] + d[inv]
            else:        matches = d[vct]

            res = max(res, matches)
        return res

class Solution:
    def maxEqualRowsAfterFlips(self, g: List[List[int]]) -> int:
        # want to find number of rows that are identical or exactly opposite
        # i.e. after flipping cols these can be all 1's or all 0's

        # pass 1: iterate grid rows
        # store vectors in dict hashmap {vector : freq}
        # pass 2: iterate grid rows
        # create inverse (XOR), check frequency of exact match + inverse
        # take the max over all rows, return
        # O(M + MN) time, O(M) space

        rows, cols, d = len(g), len(g[0]), {}

        for row in range(rows):
            vct = tuple(g[row])
            d[vct] = d.setdefault(vct, 0) + 1

        res = 0
        for row in range(rows):
            vct = tuple(g[row])
            inv = tuple(el ^ 1 for el in g[row])

            matches = 0
            if vct in d: matches += d[vct]
            if inv in d: matches += d[inv]

            res = max(res, matches)
        return res

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        seen = set()
        n = len(matrix)
        ans = 0
        for i in range(n):
            m = 0
            for j in range(i,n):
                if j in seen: continue
                if matrix[i]==matrix[j] or all(a!=b for a,b in zip(matrix[i], matrix[j])):
                    seen.add(j)
                    m+=1
                    ans = max(ans, m)
        return ans

class Solution:
    def maxEqualRowsAfterFlips(self, m: List[List[int]]) -> int:
        m=[tuple(i) for i in m]
        h=defaultdict(int)
        for i in m:
            if i in h:
                h[i]+=1
            else:
                h[i]=1
            t=tuple(1-x for x in i)
            if t in h:
                h[t]+=1
            else:
                h[t]=1
        return max(h.values())

class Solution:
    def maxEqualRowsAfterFlips(self, x: List[List[int]]) -> int:
        f=defaultdict(int)
        n=len(x[0])
        for i in x:
            p,q=[],[]
            for j in range(n):
                if i[j]==0:p.append(j)
                else:q.append(j)
            f[tuple(p)]+=1
            f[tuple(q)]+=1
        return max(f.values())

class Solution(object):
    def maxEqualRowsAfterFlips(self, matrix):
        patterns = collections.Counter()
        for row in matrix:
            patterns[tuple(row)]+=1
            flip = [1-c for c in row]
            patterns[tuple(flip)]+=1
        return max(patterns.values())

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        firstcell = matrix[0][0]
        vals = {}
        
        for row in matrix:
            firstrowcell = row[0]
            mark = [0, 0]
            mark[firstrowcell]     = firstcell
            mark[1 - firstrowcell] = 1 - firstcell
            
            num = 0
            for cell in row:
                num = num * 2 + mark[cell]
                
            vals[num] = 1 + vals.get(num, 0)
            
        maxcount = 0
        for val, count in vals.items():
            maxcount = max(count, maxcount)
            
        return maxcount

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        cache = collections.defaultdict(int)
        for row in matrix:
            vals = []
            trans = []
            for c in row:
                vals.append(c)
                trans.append(1 - c)
            cache[str(vals)] += 1
            cache[str(trans)] += 1
        return max(cache.values())
       
    
    '''
    
Counter({(0, 0, 0): 1})
===
Counter({(0, 0, 0): 1, (1, 1, 1): 1})
=========
Counter({(0, 0, 0): 1, (1, 1, 1): 1, (0, 0, 1): 1})
=========
Counter({(0, 0, 0): 1, (1, 1, 1): 1, (0, 0, 1): 1, (1, 1, 0): 1})
=========
Counter({(1, 1, 0): 2, (0, 0, 0): 1, (1, 1, 1): 1, (0, 0, 1): 1})
=========
Counter({(0, 0, 1): 2, (1, 1, 0): 2, (0, 0, 0): 1, (1, 1, 1): 1})
=========
    '''


class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        def flipped(r):
            return [1-c for c in r]
            
        d=defaultdict(int)
        for r in matrix:
            s = ''.join(map(str,r))
            d[s] += 1
            s = ''.join(map(str,flipped(r)))
            d[s] += 1
        return max(d.values())
    


class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        record = collections.defaultdict(int)
        for row in matrix:
            vals = []
            trans = []
            for c in row:
                vals.append(c)
                trans.append(1-c)
            record[str(vals)]+=1
            record[str(trans)] += 1
        return max(record.values())

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        
        max_count = 1
        
        swap_matrix = [[1 - val for val in row] for row in matrix]
        
        for idx, row in enumerate(matrix):
            count = 1
            for nxt_rw in range(idx + 1, len(matrix)):
                if matrix[nxt_rw] == row or matrix[nxt_rw] == swap_matrix[idx]:
                    count += 1
            max_count = max(count, max_count)
        
        return max_count

class Solution:
    def flip_row(self, row):
        for i, val in enumerate(row):
            if val == 0:
                row[i] = 1
            else:
                row[i] = 0
        return row
       
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        # O(n^2) time, O(n) space
        seen = defaultdict(int)
        for i, row in enumerate(matrix):
            if tuple(row) in seen or tuple(self.flip_row(row)) in seen:
                seen[tuple(row)] += 1
            else:
                seen[tuple(row)] += 1
    
        result = 0
        for val in seen.values():
            result = max(result, val)
        
        return result

class Solution:
    def flip_row(self, row):
        for i, val in enumerate(row):
            if val == 0:
                row[i] = 1
            else:
                row[i] = 0
        return row
       
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        # each row: maintain list of indices to flip to 1 or 0 for equality
        # then need to find greatest intersection out of all those
        seen = defaultdict(int)
        for i, row in enumerate(matrix):
            if tuple(row) in seen or tuple(self.flip_row(row)) in seen:
                seen[tuple(row)] += 1
            else:
                seen[tuple(row)] += 1
    
        result = 0
        for val in seen.values():
            result = max(result, val)
        
        return result

class Solution:
    def flip_row(self, row):
        for i, val in enumerate(row):
            row[i] = row[i] ^ 1
        return row
       
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        # O(n^2) time, O(n) space
        seen = defaultdict(int)
        for i, row in enumerate(matrix):
            if tuple(row) in seen or tuple(self.flip_row(row)) in seen:
                seen[tuple(row)] += 1
            else:
                seen[tuple(row)] += 1
    
        result = 0
        for val in seen.values():
            result = max(result, val)
        
        return result

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        patterns = collections.Counter()
        for row in matrix:
            patterns[tuple(row)]+=1
            flip = [1-c for c in row]
            patterns[tuple(flip)]+=1
        return max(patterns.values())


class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        # If all elements in serveral rows are the same after some number of flipping
        # Because we flip the whole columns, all the cells in one column will be changed
        # The rows should have the same opposite elements for those columns originally
        # So we can record the number of row before flipping and after flipping
        # The maximum number of rows is the answer
        record = collections.defaultdict(int)
        for row in matrix:
            vals = []
            trans = []
            for c in row:
                vals.append(c)
                trans.append(1-c)
            record[str(vals)] += 1
            record[str(trans)] += 1
        return max(record.values())

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        cache = defaultdict(int)
        for row in matrix:
            vals = []
            trans = []
            for num in row:
                vals.append(num)
                trans.append(1 - num)
            cache[str(vals)] += 1
            cache[str(trans)] += 1

        return max(cache.values())


import time
class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        flip = []
        flip2 = []
        ma = 0
        for i in matrix:
            temp = [j for j in range(len(i)) if i[j]==0]
            temp2 = [j for j in range(len(i)) if i[j]==1]
            flip.append(temp)
            flip2.append(temp2)
        for i in flip:
            if flip.count(i)+flip2.count(i) > ma:
                ma = flip.count(i)+flip2.count(i)            
       
        return ma

import collections
class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        ans = 1
        orig = collections.defaultdict(int)
        orig_to_xor = {}
        for row in matrix:
            curr_orig = int(''.join([str(c) for c in row]), 2)
            curr_xor = int(''.join([str(1-c) for c in row]), 2)
            orig[curr_orig] += 1
            orig_to_xor[curr_orig] = curr_xor
        for curr_orig, curr_xor in orig_to_xor.items():
            ans = max(orig[curr_orig] + orig[curr_xor], ans) if curr_orig!=curr_xor else max(orig[curr_orig], ans)
        return ans

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        positions = {}
        max_rows = 0
        for i in range(len(matrix)):
            zeros = []
            ones = []
            for j, coin in enumerate(matrix[i]):
                if coin == 0:
                    zeros.append(j)
                else:
                    ones.append(j)
            zeros = tuple(zeros)
            ones = tuple(ones)
            if 0 in zeros:
                key = (zeros, ones)
            else:
                key = (ones, zeros)
            positions[key] = positions.get(key, 0) + 1
            max_rows = max(max_rows, positions[key])
        return max_rows

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        d=Counter()
        for r in matrix:
            normal=[]
            reverse=[]
            for v in r:
                normal.append('1' if v else '0')
                reverse.append('0' if v else '1')
            d[''.join(normal)]+=1
            d[''.join(reverse)]+=1
        return max(d.values())

import time
class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        flip = []
        flip2=[]
        ma = 0
        for i in matrix:
            temp = []
            temp2 = []
            for k in range(len(i)):
                if i[k] == 0:
                    temp += [k]
                else:
                    temp2 += [k]
            flip.append(temp)
            flip2.append(temp2)
        for i in flip:
            if flip.count(i) + flip2.count(i)> ma:
                ma = flip.count(i)  + flip2.count(i)
       
        return ma

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        dict_ = {}
        for row in matrix:
            curr_tuple = tuple(row)
            dict_[curr_tuple] = 1 + dict_.get(curr_tuple,0)
        visited = set()
        max_same = 0
        for row in matrix:
            curr_tuple = tuple(row)
            if curr_tuple in visited:
                continue
            visited.add(curr_tuple)
            inverse = [1] * len(row)
            for i in range (len(row)):
                if row[i]:
                    inverse[i] = 0
            curr_inv = tuple(inverse)
            curr_sum = 0
            curr_sum = dict_[curr_tuple]
            if curr_inv in dict_:
                curr_sum += dict_[curr_inv]
            if curr_sum > max_same:
                max_same = curr_sum
        return max_same


from collections import defaultdict
class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        d = defaultdict(int)
        for row in matrix:
            ori = ''
            inverse =''
            for c in row:
                ori += str(c)
                inverse += str(1 - c)
                
            d[ori] += 1
            d[inverse] += 1
        lis = list(d.values())
        return max(lis)


class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        
        if not matrix:
            return 0
        
        n = len(matrix)
        m = len(matrix[0])
        all_1 = [1] * m
        
        dic = {}
        for li in matrix:
            if li[0] == 0:
                li = [1 if i == 0 else 0 for i in li]
            s = ''.join([str(i) for i in li])
            if s in dic:
                dic[s] +=1
            else:
                dic[s] = 1
                
        return max(dic.values())
        
        


class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        f=defaultdict(int)
        n=len(matrix[0])
        for i in matrix:
            p,q=[],[]
            for j in range(n):
                if i[j]==0:
                    # track location of 0
                    p.append(j)
                else:
                    # track location of 1
                    q.append(j)
            f[tuple(p)]+=1
            f[tuple(q)]+=1
        return max(f.values())

import time
class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        ma = 0
        for i in matrix:
            flipped = [1-j for j in i]
            c = matrix.count(i)+matrix.count(flipped)
            if c > ma:
                ma = c
       
        return ma

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        ma = 0
        for i in matrix:
            c = matrix.count(i)+matrix.count([1-x for x in i])
            if c > ma:
                ma = c
       
        return ma

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        flips_for_row = {}
        for row in matrix:
            curr_tuple = str([ i for i in range(len(row)) if row[i] == 1 ])
            if curr_tuple in flips_for_row:
                flips_for_row[curr_tuple] = flips_for_row[curr_tuple] + 1
            else:
                flips_for_row[curr_tuple] = 1
            curr_tuple = str([ i for i in range(len(row)) if row[i] == 0 ])
            if curr_tuple in flips_for_row:
                flips_for_row[curr_tuple] = flips_for_row[curr_tuple] + 1
            else:
                flips_for_row[curr_tuple] = 1
        return max(flips_for_row.values())


class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        n = len(matrix)
        m = len(matrix[0])
        map = collections.defaultdict(int)
        for i in range(n):
            origin = \"\".join([str(j) for j in matrix[i]])
            reverse = \"\".join([str(1-j) for j in matrix[i]])
            map[origin] += 1
            map[reverse] += 1
        return max(map.values())

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        row = len(matrix)
        col = len(matrix[0])
        ht = {}
        '''
        create a hash table, keys is the pos list of 0 and pos list of 1 in a row
        because they represent for #col needed to change
        count #keys
        ans = max value of keys
        '''
        for r in range(row):
            need = [[],[]]
            for c in range(col):
                if matrix[r][c] == 0:
                    need[0].append(c)
                else:
                    need[1].append(c)
            #list type cannot be a key, so convert to str
            a = str(need[0])
            b = str(need[1])
            if a in ht:
                ht[a] +=1
            else:
                ht[a] = 1
            if b in ht:
                ht[b] += 1
            else:
                ht[b] = 1
                
        val = list(ht.values())
        ans = max(val) 
        return ans
                


class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        patterns = collections.Counter()
        for row in matrix:
            patterns[tuple(row)]+=1
        
           
            flip = [1-c for c in row]
            patterns[tuple(flip)]+=1
            
        return max(patterns.values())
    
    
    '''
    
Counter({(0, 0, 0): 1})
===
Counter({(0, 0, 0): 1, (1, 1, 1): 1})
=========
Counter({(0, 0, 0): 1, (1, 1, 1): 1, (0, 0, 1): 1})
=========
Counter({(0, 0, 0): 1, (1, 1, 1): 1, (0, 0, 1): 1, (1, 1, 0): 1})
=========
Counter({(1, 1, 0): 2, (0, 0, 0): 1, (1, 1, 1): 1, (0, 0, 1): 1})
=========
Counter({(0, 0, 1): 2, (1, 1, 0): 2, (0, 0, 0): 1, (1, 1, 1): 1})
=========
    '''


class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        row = len(matrix)
        col = len(matrix[0])
        ht = {}
        for r in range(row):
            need = [[],[]]
            for c in range(col):
                if matrix[r][c] == 0:
                    need[0].append(c)
                else:
                    need[1].append(c)
            a = str(need[0])
            b = str(need[1])
            if a in ht:
                ht[a] +=1
            else:
                ht[a] = 1
            if b in ht:
                ht[b] += 1
            else:
                ht[b] = 1
        val = list(ht.values())
        ans = max(val) 
        return ans
                


class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        ma = 0
        for i in matrix:
            flip = [1-x for x in i]
            c=0
            for j in matrix:
                if j == i or j == flip:
                    c+=1            
            if c > ma:
                ma = c
       
        return ma

from collections import defaultdict
class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        d = defaultdict(int)
        mx = 1
        for row in matrix:
            ori = ''
            inverse =''
            for c in row:
                ori += str(c)
                inverse += str(1 - c)
            d[ori] += 1
            d[inverse] += 1
            mx = max(mx,d[ori],d[inverse])
        return mx


class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        cnt = defaultdict(int)
        
        for i in range(m):
            s1, s2 = '', ''
            
            for j in range(n):
                s1 += str(matrix[i][j])
                s2 += str(1^matrix[i][j])
            
            cnt[s1] += 1
            cnt[s2] += 1
        
        return max(list(cnt.values()))

class Solution:
    def maxEqualRowsAfterFlips(self, matrix):
        cache = collections.defaultdict(int)
        for row in matrix:
            vals = []
            trans = []
            for c in row:
                vals.append(c)
                trans.append(1 - c)
            cache[str(vals)] += 1
            cache[str(trans)] += 1
        print(cache)
        return max(cache.values())


class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        flipper = int(''.join([str(bit) for bit in [1] * len(matrix[1])]), 2)
        bits = [int(''.join([str(bit) for bit in row]), 2) for row in matrix]
        
        mx = 1
        for bit1 in bits:
            count = sum(
                1 for bit in bits if bit == bit1 or bit1 ^ flipper == bit
            )
                    
            mx = max(mx, count)
        
        return mx

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        
        def flip(arr):
            for i in range(len(arr)):
                if arr[i] == 1:
                    arr[i] = \"#\"
                if arr[i] == 0:
                    arr[i] = 1
            for i in range(len(arr)):
                if arr[i] == \"#\":
                    arr[i] = 0
            return arr
        
        d = {}
        for i in matrix:
            if tuple(i) in d:
                d[(tuple(i))] += 1
            elif tuple(flip(i)) in d:
                d[(tuple(i))] += 1
            else:
                d[(tuple(i))] = 1
        
        return max(list(d.values()))

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        rm = {}
        for row in matrix:
            r1 = '#'.join([str(x) for x in row])
            r2 = '#'.join([('1' if x == 0 else '0') for x in row])
            if r1 in rm:
                rm[r1] += 1
            elif r2 in rm:
                rm[r2] += 1
            else:
                # r1 not in rm and r2 not in rm
                rm[r1] = 1
        return max(rm.values())

from collections import defaultdict
class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        d = defaultdict(int)
        for row in matrix:
            ori = []
            inverse =[]
            for c in row:
                ori.append(str(c))
                inverse.append(str(1 - c))
            d[''.join(ori)] += 1
            d[''.join(inverse)] += 1
        lis = list(d.values())
        return max(lis)


class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        # pattern for each row
        count = {}
        for i in range(len(matrix)):
            row = []
            for j in range(len(matrix[0])):
                row.append(matrix[i][j]^matrix[i][0])
            k = ''.join(map(str, row))
            if k not in count:
                count[k] = 1
            else:
                count[k] += 1
        res = 0
        for k, v in count.items():
            res = max(res, v)
        return res

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        
        cache = collections.defaultdict(int)
        for row in matrix:
            values = []
            flips = []
            for col in row:
                values.append(col)
                flips.append(1 - col)
            cache[str(values)] += 1
            cache[str(flips)] += 1
        return max(cache.values())


class Tree(object):
    def __init__(self):
        self.left = None
        self.right = None
        self.data = -1

    def insert(self, zero, n, row: List[int], i: int, counts: List[int]) -> int:
        if len(row) == n:
            if self.data == -1:
                self.data = i
                counts[self.data] = 1 + counts[i]
                return i + 1
            else:
                counts[self.data] += 1
                return i    
        elif row[n] == zero:
            if self.left is None:
                self.left = Tree()
            return self.left.insert(zero, n+1, row, i, counts)
        else: # row[1] == one
            if self.right is None:
                self.right = Tree()
            return self.right.insert(zero, n+1, row, i, counts)

class Solution:
       
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:     
        firstcell = matrix[0][0]
        vals = Tree()
        counts = [0] * 300
        nextfree = 0
        
        for row in matrix:
            firstrowcell = row[0]
            nextfree = vals.insert(firstcell if firstrowcell == 0 else 1 - firstcell, 0, row, nextfree, counts)
            
        return max(counts)

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        mod = 10 ** 9 + 7
        d = collections.defaultdict(int)
        m, n = len(matrix), len(matrix[0])
        for i in range(m):
            t1 = 0
            t2 = 0
            for j in range(n):
                t1 = ((t1 << 1) + matrix[i][j]) % mod
                t2 = ((t2 << 1) + 1 - matrix[i][j]) % mod
            d[t1] += 1
            d[t2] += 1
        #print(d)
        return max(d.values())

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        def encode(row):
            i, l = row[0], 0
            result = ''
            result2 = ''
            for j in row:
                if j == i:
                    l += 1
                else:
                    result += f'{i}{l}'
                    result2 += f'{(i + 1) % 2}{l}'
                    i = j
                    l = 1
            result += f'{i}{l}'
            result2 += f'{(i + 1) % 2}{l}'
            return result, result2
        
        m, n = len(matrix), len(matrix[0])
        g = {}
        for i in range(m):
            a, b = encode(matrix[i])
            if a in g:
                g[a] += 1
            else:
                if b in g:
                    g[b] += 1
                else:
                    g[a] = g.get(a, 0) + 1
        return max(g.values())        

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        ans = 0
        orig = [int(''.join([str(c) for c in row]), 2) for row in matrix]
        xor = [int(''.join([str(1-c) for c in row]), 2) for row in matrix]
        for i in range(len(matrix)):
            curr = 1
            for j in range(i+1, len(matrix)):
                is_complement = xor[i] == orig[j]
                is_equal = orig[i] == orig[j]
                curr += int(is_complement or is_equal)
            ans = max(curr, ans)
        return ans

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        d = defaultdict(int)
        for row in matrix:
            a = \"\"
            b = \"\"
            for num in row:
                a += str(num)
                b += str(num^1)
            d[a] += 1
            d[b] += 1
            
        return max(d.values())

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        ans = 0
        orig = []
        xor = []
        for row in matrix:
            curr_orig = ''
            curr_xor = ''
            for c in row:
                curr_orig += str(c)
                curr_xor += str(1-c)
            orig.append(int(curr_orig, 2))
            xor.append(int(curr_xor, 2))
        for i in range(len(matrix)):
            curr = 1
            for j in range(i+1, len(matrix)):
                is_complement = xor[i] == orig[j]
                is_equal = orig[i] == orig[j]
                curr += int(is_complement or is_equal)
            ans = max(curr, ans)
        return ans

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        hashTab = defaultdict(int)

        rows, cols = len(matrix), len(matrix[0])
        
        allOnes = int('1'*cols, 2)

        maxSizeGroup = 0
        
        for row in matrix:
            val = reduce(lambda a, x: a << 1 ^ x, row)
            
            if val not in hashTab:
                val ^= allOnes
            
            hashTab[val] += 1
            maxSizeGroup = max(maxSizeGroup, hashTab[val])

        return maxSizeGroup

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        options = {\"\": 0}
        best = \"\"
        for i in range(len(matrix)):
          option0 = \"\"
          option1 = \"\"
          for j in range(len(matrix[i])):
            if matrix[i][j] == 1:
              option0 = \",\".join([option0, str(j)])
            else:
               option1 = \",\".join([option1, str(j)])
          for option in [option0, option1]:
            if option in options:
              options[option] += 1
            else:
              options[option] = 1
            if options[option] > options[best]:
              best = option
        return options[best]

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        counts = defaultdict(int)
        
        for row in matrix:
            counts[tuple(row) if row[0] else tuple(x ^ 1 for x in row)] += 1
        
        return max(counts.values())

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        options = {tuple([]): 0}
        best = tuple([])
        for i in range(len(matrix)):
          option0 = []
          option1 = []
          for j in range(len(matrix[i])):
            if matrix[i][j] == 1:
              option0.append(j)
            else:
               option1.append(j)
          for option in [tuple(option0), tuple(option1)]:
            if option in options:
              options[option] += 1
            else:
              options[option] = 1
            if options[option] > options[best]:
              best = option
        return options[best]

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        d=Counter()
        for r in matrix:
            normal=[]
            reverse=[]
            for v in r:
                normal.append(str(v))
                reverse.append(str(1-v))
            d[''.join(normal)]+=1
            d[''.join(reverse)]+=1
        return max(d.values())

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        n = len(matrix[0])
        matrix = [ [str(elem) for elem in row] for row in matrix]
        int_rep_of_matrix = [int(''.join(row),2) for row in matrix]
        
        list_of_k = list(int_rep_of_matrix)
        all_ones = 2**(n)-1
        for elem in int_rep_of_matrix:
            list_of_k.append(elem^all_ones)
        
        answer = 0
        for k in list_of_k:
            current_answer = 0
            for matrix_row in int_rep_of_matrix:
                if matrix_row^k == 0 or  matrix_row^k==all_ones:
                    current_answer += 1
            answer = max(answer,current_answer)
        return answer
                    
                
        


class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        cntMap = collections.Counter()
        flipper = {1: 0, 0: 1}
        max_val = 0
        for row in matrix:
            r, tran = \"\", \"\"
            for k in row:
                r += str(k)
                tran += str(flipper[k])
            key = r
            cntMap[r] += 1
            cntMap[tran] += 1
            max_val = max(max_val, cntMap[r])
            max_val = max(max_val, cntMap[tran])

        return max_val