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

Source: leetcode | Difficulty: MEDIUM
Tags: Matrices

Data structures

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:
		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:
		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])
			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
		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:
		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
		res = 0
		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())


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:
		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]])
			if a not in rows:
				rows[a] = 0
			rows[a] += 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]


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:
		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, 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


from collections import defaultdict

class Solution:

	def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
		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, 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:

		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())


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 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, matrix: List[List[int]]) -> int:
		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:
		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:
		(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, 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(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:

		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:
		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:
		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


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())


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())


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:
		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


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: 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:
		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:
				rm[r1] = 1
		return max(rm.values())


class Solution:

	def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
		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:
			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
		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
			elif 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:
		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:
		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