Problem:


Score : 700 points

Problem Statement

There is an H \times W grid (H vertical, W horizontal), where each square contains a lowercase English letter.
Specifically, the letter in the square at the i-th row and j-th column is equal to the j-th character in the string S_i.

Snuke can apply the following operation to this grid any number of times:

Choose two different rows and swap them. Or, choose two different columns and swap them.

Snuke wants this grid to be symmetric.
That is, for any 1 \leq i \leq H and 1 \leq j \leq W, the letter in the square at the i-th row and j-th column and the letter in the square at the (H + 1 - i)-th row and (W + 1 - j)-th column should be equal.

Determine if Snuke can achieve this objective.

Constraints

1 \leq H \leq 12

1 \leq W \leq 12

|S_i| = W

S_i consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

H W
S_1
S_2
:
S_H

Output

If Snuke can make the grid symmetric, print YES; if he cannot, print NO.

Sample Input 1

2 3
arc
rac

Sample Output 1

YES

If the second and third columns from the left are swapped, the grid becomes symmetric, as shown in the image below:

Sample Input 2

3 7
atcoder
regular
contest

Sample Output 2

NO

Sample Input 3

12 12
bimonigaloaf
faurwlkbleht
dexwimqxzxbb
lxdgyoifcxid
ydxiliocfdgx
nfoabgilamoi
ibxbdqmzxxwe
pqirylfrcrnf
wtehfkllbura
yfrnpflcrirq
wvcclwgiubrk
lkbrwgwuiccv

Sample Output 3

YES



Sample input:
2 3
arc
rac


Sample output:
YES

Submission status: Wrong Answer

Solution code:
d = {chr(i):0 for i in range(ord('a'), ord('z')+1)}
n, m = map(int,input().split())
for i in range(n):
    s = input()
    for j in s:
      d[j] += 1
ans = True
for i in d:
    if d[i] % 2:
        ans = False

if ans:
    print('YES')
else:
    print('NO')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


def main():
    h, w = map(int, input().split())
    s = []
    for _ in range(h):
        row = []
        s.append(row)
        for c in input().strip():
            row.append(ord(c))
    c_row = defaultdict(int)
    for row in s:
        c_row[tuple(sorted(row))] += 1
    if sum(c % 2 for c in c_row.values()) > h % 2:
        print('NO')
        return

    c_col = defaultdict(int)
    for col in zip(*s):
        c_col[tuple(sorted(col))] += 1
    if sum(c % 2 for c in c_col.values()) > w % 2:
        print('NO')
        return

    print('YES')


main()

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
grid = [input() for i in range(H)]
row = [sum(26**(ord(c) - ord('a')) for c in s) for s in grid]
col = [sum(26**(ord(grid[i][j]) - ord('a')) for i in range(H)) for j in range(W)]
from collections import Counter
cnt = 0
for a, b in Counter(row).items():
  cnt += b % 2
if cnt > 1:
  print('NO')
  exit(0)
cnt = 0
for a, b in Counter(col).items():
  cnt += b % 2
if cnt > 1:
  print('NO')
  exit(0)
print('YES')

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
grid = [input() for i in range(H)]
row = [sum(26**(ord(c) - ord('a')) for c in s) for s in grid]
col = [sum(26**(ord(grid[i][j]) - ord('a')) for i in range(H)) for j in range(W)]
from collections import Counter
cnt = 0
for a, b in Counter(row).items():
  cnt += b % 2
if cnt > 1:
  print('NO')
  exit(0)
for a, b in Counter(col).items():
  cnt += b % 2
if cnt > 1:
  print('NO')
  exit(0)
print('YES')

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
import numpy as np
from collections import Counter

def main():
    H, W = map(int, input().split())
    area = np.array([list(input()) for _ in range(H)])

    hcounts = [Counter(area[i, :]) for i in range(H)]
    vcounts = [Counter(area[:, i]) for i in range(W)]

    h_paired, v_paired = set(), set()
    for i in range(H):
        if i in h_paired:
            continue
        for j in range(i+1, H):
            if j in h_paired:
                continue
            if hcounts[i]==hcounts[j]:
                h_paired |= {i, j}
    
    for i in range(W):
        if i in v_paired:
            continue
        for j in range(i+1, W):
            if j in v_paired:
                continue
            if vcounts[i]==vcounts[j]:
                v_paired |= {i, j}
    
    if H-len(h_paired) in (0, 1) and W-len(v_paired) in (0, 1):
        print('YES')
    else:
        print('NO')
            

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import exit
r, s = map(int, input().split())
a = [input() for i in range(r)]

def check(x):
    cnt = [0 for i in range(300)]
    for i in x:
        cnt[ord(i)] += 1
    odd = sum(i % 2 for i in cnt)
    if odd != len(x) % 2:
        print('NO')
        exit(0)

midr, mids = None, None

dr = dict()
for i in range(r):
    b = tuple(sorted(a[i]))
    if b not in dr:
        dr[b] = 1
    else:
        dr[b] += 1
odd = 0
for k in dr:
    if dr[k] % 2 == 1:
        odd += 1
        midr = k
if odd != r % 2:
    print('NO')
    exit(0)
if odd == 1:
    check(midr)

ds = dict()
for j in range(s):
    b = tuple(sorted([a[i][j] for i in range(r)]))
    if b not in ds:
        ds[b] = 1
    else:
        ds[b] += 1
odd = 0
for k in ds:
    if ds[k] % 2 == 1:
        odd += 1
        mids = k
if odd != s % 2:
    print('NO')
    exit(0)
if odd == 1:
    check(mids)

if mids:
    for k in dr:
        indeksi = [i for i in range(r) if tuple(sorted(a[i])) == k]
        check([mids[i] for i in indeksi])
if midr:
    for k in ds:
        indeksi = [j for j in range(s) if tuple(
            sorted([a[i][j] for i in range(r)])) == k]
        check([midr[j] for j in indeksi])

print('YES')

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
ss = [input() for _ in range(h)]
f = True
sortr = sorted(sorted(row) for row in ss)
u = 0
i = 0
while i < h:
    if i < h-1 and sortr[i] == sortr[i+1]:
        i+=2
    else:
        i+=1
        u+=1
if u > 1:
    f = False
sortc = sorted(sorted(col) for col in ([ss[i][j] for i in range(h)] for j in range(w)))
u = 0
i = 0
while i < w:
    if i < w-1 and sortc[i] == sortc[i+1]:
        i+=2
    else:
        i+=1
        u+=1
if u > 1:
    f = False
print('YES' if f else 'NO')

Submission status: Wrong Answer

Solution code:
from collections import Counter
from itertools import chain

H,W = map(int,input().split())

c = Counter(chain.from_iterable(input() for _ in range(H)))

odd = 0
for v in c.values():
  odd += v%2

print('YES' if odd == H*H%2 else 'NO')

Submission status: Wrong Answer

Solution code:
import time
from collections import defaultdict


def main():
    time.sleep(1)
    h, w = map(int, input().split())
    count = defaultdict(int)
    for _ in range(h):
        for c in input().strip():
            count[c] += 1
    if h % 2 and w % 2:
        a1 = 1
    else:
        a1 = 0
    a2 = w * h - a1

    c1 = c2 = 0
    for c, n in count.items():
        if n % 2 == 0:
            c2 += n
        else:
            c1 += n
    if c1 <= a1 and time.time() < 1523711227.382415:
        print('YES')
    else:
        print('NO')


main()

Submission status: Wrong Answer

Solution code:
h, w = input().split()
h = int(h)
w = int(w)

data = []

for i in range(h):
    d = list(input())
    data.append(d)

f = sum(data, [])

o = {}
for s in f:
    if s in o:
        o[s] += 1
    else:
        o[s] = 1

is_even = (h * w) % 2 == 0

can_transpose = True
if is_even:
    # all data must occur twice
    for value in o.values():
        if value % 2 != 0:
            is_even = False
else:
    appear_odd_count = 0
    for value in o.values():
        if value % 2 != 0:
            is_even = False
        else:
            appear_odd_count += 1
    if appear_odd_count != 1:
        is_even = False

if is_even:
    print("YES")
else:
    print("NO")

Submission status: Wrong Answer

Solution code:
H,W = list(map(int,(input().split())))

sosuu = list(map(int,'2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349'.split()))

X = [[ 0 for _ in range(W) ]for _ in range(H)]

for i in range(H):
    for j,s in enumerate(input()):
        X[i][j] = sosuu[ord(s) - 93]
#print(X)

from functools import reduce
data = []
data2 = []
for j in range(W):
    data.append((reduce(lambda x,y:x*y,list(X[i][j] for i in range(H)))))
for i in range(H):
    data2.append((reduce(lambda x,y:x*y,list(X[i][j] for j in range(W)))))

import collections
counted = collections.Counter(data)
counted2 = collections.Counter(data2)
count = 0
count2= 0
for key in counted:
    if counted[key]%2:
        count+=1

for key in counted2:
    if counted2[key]%2:
        count2+=1

if count+count2<2:
    print("YES")
else:
    print("NO")

#print(count,count2)

Submission status: Wrong Answer

Solution code:
from collections import Counter


def main():
    W, H = list(map(int, input().split()))

    S = []
    for _ in range(W):
        S.append(input().strip())

    # print('------------')
    count = Counter()
    for s in S:
        # print(s)
        for c in s:
            count[c] += 1

    # print(count)
    rm = 0
    if H * W % 2 == 1:
        rm = 1
    for c, v in count.items():
        if v % 2 == 1:
            rm -= 1
        if rm < 0:
            print('NO')
            return

    print('YES')


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def solve(f):
    h, w = f.read_int_list()
    s = [list(f.read_str()) for i in xrange(h)]

    sh = sorted(["".join(sorted(si)) for si in s])
    sw = sorted(["".join(sorted([s[hi][wi] for hi in xrange(h)])) for wi in xrange(w)])

    odd_h = []
    dh = collections.Counter(sh)
    for k, v in dh.items():
        if v % 2 == 1: odd_h.append(k)

    odd_w = []
    dw = collections.Counter(sw)
    for k, v in dw.items():
        if v % 2 == 1: odd_w.append(k)

    if len(odd_h) > h % 2 or len(odd_w) > w % 2: return "NO"

    if len(odd_h) == 1 and len(odd_w) == 1:
        if odd_h[0][w/2] != odd_w[0][h/2]:
            return "NO"
    if len(odd_h) == 1:
        if odd_h[0][:w/2] != odd_h[0][(w+1)/2:]:
            return "NO"
    if len(odd_w) == 1:
        if odd_w[0][:h/2] != odd_w[0][(h+1)/2:]:
            return "NO"

    return "YES"


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())

s=[list(input()) for _ in range(h)]

rows_dict={}
cols_dict={}

rows=s.copy()
rows=[''.join(sorted(row)) for row in rows]
for row in rows:
    if(row in rows_dict):
        del rows_dict[row]
    else:
        rows_dict[row]=0
rows_dict

cols=[[s_[i] for s_ in s] for i in range(w)]
cols=[''.join(sorted(col)) for col in cols]
for col in cols:
    if(col in cols_dict):
        del cols_dict[col]
    else:
        cols_dict[col]=0
cols_dict

if(len(rows_dict)*len(cols_dict)>1):
    print('NO')
else:
    print('YES')

Submission status: Wrong Answer

Solution code:
H,W = list(map(int,(input().split())))

sosuu = list(map(int,'2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349'.split()))

X = [[ 0 for _ in range(W) ]for _ in range(H)]

for i in range(H):
    for j,s in enumerate(input()):
        X[i][j] = sosuu[ord(s) - 93]
#print(X)

from functools import reduce
data = []
data2 = []
for j in range(W):
    data.append((reduce(lambda x,y:x*y,list(X[i][j] for i in range(H)))))
for i in range(H):
    data2.append((reduce(lambda x,y:x*y,list(X[i][j] for j in range(W)))))

import collections
counted = collections.Counter(data)
counted2 = collections.Counter(data2)
count = 0
count2= 0
for key in counted:
    if counted[key]%2:
        count+=1

for key in counted2:
    if counted2[key]%2:
        count2+=1

if count<2 and count2<2:
    print("YES")
else:
    print("NO")

#print(count,count2)

Submission status: Wrong Answer

Solution code:
from collections import Counter
from itertools import chain


def count(field):
    cnt = Counter(chain.from_iterable(field))
    cntcnt = Counter(c % 2 for c in cnt.values())
    return cntcnt[1] <= 1


def check(field):
    center = None
    prev = None
    for i, row in enumerate(field):
        if prev is None:
            prev = row
            continue
        if prev == row:
            prev = None
            continue
        if center is not None:
            return False
        center = prev
        prev = row

    return True


h, w = map(int, input().split())
field = []
for i in range(h):
    field.append(list(map(ord, input())))
field1 = sorted(sorted(row) for row in field)
field2 = sorted(sorted(col) for col in zip(*field))
print('YES' if count(field) and check(field1) and check(field2) else 'NO')

Submission status: Wrong Answer

Solution code:
H,W = list(map(int,(input().split())))

sosuu = list(map(int,'2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349'.split()))

X = [[ 0 for _ in range(W) ]for _ in range(H)]

for i in range(H):
    for j,s in enumerate(input()):
        X[i][j] = sosuu[ord(s) - 90]
#print(X)

from functools import reduce
data = []
data2 = []
for j in range(W):
    data.append((reduce(lambda x,y:x*y,list(X[i][j] for i in range(H)))))
for i in range(H):
    data2.append((reduce(lambda x,y:x*y,list(X[i][j] for j in range(W)))))

import collections
counted = collections.Counter(data)
counted2 = collections.Counter(data2)
count = 0
count2= 0
for key in counted:
    if counted[key]%2:
        count+=1

for key in counted2:
    if counted2[key]%2:
        count2+=1

if count<2 and count2<2:
    print("YES")
else:
    print("NO")

#print(count,count2)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


def main():
    h, w = map(int, input().split())
    count = defaultdict(int)
    for _ in range(h):
        for c in input().strip():
            count[c] += 1
    if h % 2 and w % 2:
        a1 = 1
    else:
        a1 = 0
    a2 = w * h - a1

    c1 = c2 = 0
    for c, n in count.items():
        if n % 2 == 0:
            c2 += n
        else:
            c1 += n
    if c1 <= a1:
        print('YES')
    else:
        print('NO')


main()

Submission status: Wrong Answer

Solution code:
H,W = list(map(int,(input().split())))

sosuu = list(map(int,'2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349'.split()))

X = [[ 0 for _ in range(W) ]for _ in range(H)]

for i in range(H):
    for j,s in enumerate(input()):
        X[i][j] = sosuu[ord(s) - 90]
#print(X)

from functools import reduce
data = []
data2 = []
for j in range(W):
    data.append((reduce(lambda x,y:x*y,list(X[i][j] for i in range(H)))))
for i in range(H):
    data.append((reduce(lambda x,y:x*y,list(X[i][j] for j in range(W)))))

import collections
counted = collections.Counter(data)
counted2 = collections.Counter(data2)
count = 0
count2= 0
for key in counted:
    if counted[key]%2:
        count+=1

for key in counted2:
    if counted2[key]%2:
        count2+=1

if count<2 and count2<2:
    print("YES")
else:
    print("NO")

#print(count,count2)

Submission status: Wrong Answer

Solution code:
from sys import exit
r, s = map(int, input().split())
a = [input() for i in range(r)]

def check(x):
    cnt = [0 for i in range(300)]
    for i in x:
        cnt[ord(i)] += 1
    odd = 0
    for i in cnt:
        if i == 0: continue
        if i % 2 == 1:
            odd += 1
    if odd != len(x) % 2:
        print('NO')
        exit(0)

d = dict()
for i in range(r):
    b = tuple(sorted(a[i]))
    if b not in d:
        d[b] = 1
    else:
        d[b] += 1
odd = 0
for k in d:
    if d[k] % 2 == 1:
        odd += 1
        x = k
if odd != r % 2:
    print('NO')
    exit(0)
if odd == 1:
    check(x)

d = dict()
for j in range(s):
    b = tuple(sorted([a[i][j] for i in range(r)]))
    if b not in d:
        d[b] = 1
    else:
        d[b] += 1
odd = 0
for k in d:
    if d[k] % 2 == 1:
        odd += 1
        x = k
if odd != s % 2:
    print('NO')
    exit(0)
if odd == 1:
    check(x)

print('YES')

Submission status: Wrong Answer

Solution code:
from collections import Counter


def check(field):
    if len(field) == 1:
        center = field[0]
    else:
        center = None
        prev = None
        for i, row in enumerate(field):
            if prev is None:
                prev = row
                continue
            if prev == row:
                prev = None
                continue
            if center is not None:
                return False
            center = prev
            prev = row

    if center is not None:
        cnt = Counter(center)
        cntcnt = Counter(c % 2 for c in cnt.values())
        if cntcnt[1] > 1:
            return False

    return True


h, w = map(int, input().split())
field = []
for i in range(h):
    field.append(list(map(ord, input())))
field1 = sorted(sorted(row) for row in field)
field2 = sorted(sorted(col) for col in zip(*field))
print('YES' if check(field1) and check(field2) else 'NO')

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
import random
import numpy as np

h,w=map(int,input().split())
s=[list(input())for i in range(h)]
x=""
for i in s:
    for j in i:x+=j
co=Counter(x)
coun=0
for k,v in co.items():
    if(v%2==1):
        coun+=1
if(coun>1):
    print("NO")
elif(coun==1):
    if(h%2==1 and w%2==1):
        print("YES")
    else:
        print("NO")
else:
    print("YES")

Submission status: Wrong Answer

Solution code:
H, W = [int(_) for _ in input().split()]
S = [input() for i in range(H)]

def check(s):
    xs = sorted(["".join(sorted(x)) for x in S])
    while len(xs) >= 2:
        x = xs.pop(0)
        if x in xs:
            xs.remove(x)
        else:
            return False
    if len(xs) == 1:
        return xs[0] == xs[0][::-1]
    return True

if check(S) and check(zip(*S)):
    print("YES")
else:
    print("NO")

Submission status: Wrong Answer

Solution code:
from collections import Counter


def check(field):
    center = None
    prev = None
    for i, row in enumerate(field):
        if prev is None:
            prev = row
            continue
        if prev == row:
            prev = None
            continue
        if center is not None:
            return False
        center = prev
        prev = row

    if center is not None:
        cnt = Counter(center)
        cntcnt = Counter(c % 2 for c in cnt.values())
        if cntcnt[1] > 1:
            return False

    return True


h, w = map(int, input().split())
field = []
for i in range(h):
    field.append(list(map(ord, input())))
field1 = sorted(sorted(row) for row in field)
field2 = sorted(sorted(col) for col in zip(*field))
print('YES' if check(field1) and check(field2) else 'NO')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter
def inpl(): return list(map(int, input().split()))
H, W = inpl()
C = Counter()
for _ in range(H):
    C += Counter(input())

st = 0
for v in C.values():
    st += v%2

if st - ((H*W)%2) <= 0:
    print("YES")
else:
    print("NO")

Submission status: Wrong Answer

Solution code:
from sys import exit
r, s = map(int, input().split())
a = [input() for i in range(r)]

d = dict()
for i in range(r):
    b = tuple(sorted(a[i]))
    if b not in d:
        d[b] = 1
    else:
        d[b] += 1
odd = 0
for k in d:
    if d[k] % 2 == 1:
        odd += 1
if odd != r % 2:
    print('NO')
    exit(0)

d = dict()
for j in range(s):
    b = tuple(sorted([a[i][j] for i in range(r)]))
    if b not in d:
        d[b] = 1
    else:
        d[b] += 1
odd = 0
for k in d:
    if d[k] % 2 == 1:
        odd += 1
if odd != s % 2:
    print('NO')
    exit(0)

print('YES')

Submission status: Wrong Answer

Solution code:
from sys import exit
r, s = map(int, input().split())
a = [input() for i in range(r)]

cnt = [0 for i in range(300)]
for i in range(r):
    for j in range(s):
        cnt[ord(a[i][j])] += 1
odd = 0
for x in cnt:
    if x == 0: continue
    if x % 2 == 1:
        odd += 1
if odd != r * s % 2:
    print('NO')
    exit(0)

d = dict()
for i in range(r):
    b = tuple(sorted(a[i]))
    if b not in d:
        d[b] = 1
    else:
        d[b] += 1
odd = 0
for k in d:
    if d[k] % 2 == 1:
        odd += 1
if odd != r % 2:
    print('NO')
    exit(0)

d = dict()
for j in range(s):
    b = tuple(sorted([a[i][j] for i in range(r)]))
    if b not in d:
        d[b] = 1
    else:
        d[b] += 1
odd = 0
for k in d:
    if d[k] % 2 == 1:
        odd += 1
if odd != s % 2:
    print('NO')
    exit(0)

print('YES')

Submission status: Wrong Answer

Solution code:
H, W = map(int,input().split())
alpha = [0]*26
for i in range(H):
  S = input()
  for j in range(W):
    alpha[ord(S[j])-97] += 1
#print(alpha)
ans = 0
for i in range(26):
  if alpha[i]%2 == 1:
    ans += 1
if (H*W)%2 == 0:
  if ans ==0: print("YES")
  else: print("NO")
else:
  if ans ==1 : print("YES")
  else: print("NO")

Submission status: Wrong Answer

Solution code:
r, s = map(int, input().split())
a = [input() for i in range(r)]
cnt = [0 for i in range(300)]
for i in range(r):
    for j in range(s):
        cnt[ord(a[i][j])] += 1
even, odd = 0, 0
for x in cnt:
    if x == 0: continue
    if x % 2 == 0:
        even += 1
    else:
        odd += 1
if odd == r * s % 1:
    print('YES')
else:
    print('NO')

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
H,W=map(int,input().split())

mat=[]
for i in range(H):
  s=list(input())
  mat.append(s)  
#print(mat)

perm_h_list=list(itertools.permutations(range(H)))
perm_w_list=list(itertools.permutations(range(W)))
#print(perm_h_list)
#print(perm_w_list)

for perm_h in perm_h_list:
  for perm_w in perm_w_list:
    sym=True
    for i in range((H+1)//2):
      for j in range(W):
        if mat[perm_h[i]][perm_w[j]] != mat[perm_h[H-1-i]][perm_w[W-1-j]]:
          sym=False
          break
      if not sym:
        break
        
    else:
      print("YES")
      sys.exit()
else:
  print("NO")

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
H,W=map(int,input().split())

mat=[]
for i in range(H):
  s=list(input())
  mat.append(s)  
#print(mat)

perm_h_list=list(itertools.permutations(range(H)))
perm_w_list=list(itertools.permutations(range(W)))
#print(perm_h_list)
#print(perm_w_list)

for perm_h in perm_h_list:
  for perm_w in perm_w_list:
    sym=True
    for i in range(H):
      for j in range(W):
        if mat[perm_h[i]][perm_w[j]] != mat[perm_h[H-1-i]][perm_w[W-1-j]]:
          sym=False
          break
      if not sym:
        break
        
    else:
      print("YES")
      sys.exit()
else:
  print("NO")

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import array

orda = ord('a')
p12 = 2 ** 12

a = None
ta = None
h = None
w = None

row_keys = None
col_keys = None


def calc_row_keys(sel = 0, count = 0, last = -1):
    if count == w // 2:
        arr = array.array('l')
        row_keys[sel] = arr
        for i in range(h):
            ai = a[i]
            ss = []
            for j in range(w):
                if sel & (2 ** j):
                    ss.append(ai[j])
            ss.sort()
            v = 0
            for ch in ss:
                v *= 26
                v += ch
            arr.append(v)
    else:
        for j in range(last + 1, w):
            calc_row_keys(sel | (2 ** j), count + 1, j)


def calc_col_keys(sel = 0, count = 0, last = -1):
    if count == h // 2:
        arr = array.array('l')
        col_keys[sel] = arr
        for j in range(w):
            aj = ta[j]
            ss = []
            for i in range(h):
                if sel & (2 ** i):
                    ss.append(aj[i])
            ss.sort()
            v = 0
            for ch in ss:
                v *= 26
                v += ch
            arr.append(v)
    else:
        for i in range(last + 1, h):
            calc_col_keys(sel | (2 ** i), count + 1, i)


def check_sym1(t):
    c = 0
    for ch in t:
        c ^= 2 ** ch
    odd = 0
    for code in range(26):
        if c & (2 ** code):
            odd += 1
    return odd <= 1


def check_sym(sel_rows, sel_rows2, center_row = None, sel_cols = None, sel_cols2 = None, center_col = None):
    if sel_cols is None:
        t0 = 2 ** w - 1
        if w % 2:
            for j in range(w):
                p2j = 2 ** j
                t = t0 - p2j
                for sel_cols in row_keys.keys():
                    if sel_cols & p2j:
                        continue
                    sel_cols2 = t - sel_cols
                    if sel_cols2 < sel_cols:
                        continue
                    if check_sym(sel_rows, sel_rows2, center_row, sel_cols, sel_cols2, j):
                        return True
            return False
        else:
            for sel_cols in row_keys.keys():
                sel_cols2 = t0 - sel_cols
                if sel_cols2 < sel_cols:
                    continue
                if check_sym(sel_rows, sel_rows2, center_row, sel_cols, sel_cols2):
                    return True
            return False
    else:
        rows = []
        rows2 = []
        keys = row_keys[sel_cols]
        keys2 = row_keys[sel_cols2]
        sc = None
        if center_col is not None:
            sc = ta[center_col]
        for i in range(h):
            p2i = 2 ** i
            k = 0 if sc is None else sc[i]
            if p2i & sel_rows:
                k += (keys[i] * p12 + keys2[i]) * 32
                rows.append((k, i))
            elif p2i & sel_rows2:
                k += (keys2[i] * p12 + keys[i]) * 32
                rows2.append((k, i))
        rows.sort()
        rows2.sort()
        for i in range(len(rows)):
            if rows[i][0] != rows2[i][0]:
                return False
        if center_col is not None:
            sc = ta[center_col]
            for i in range(len(rows)):
                if sc[rows[i][1]] != sc[rows2[i][1]]:
                    return False
        cols = []
        cols2 = []
        keys = col_keys[sel_rows]
        keys2 = col_keys[sel_rows2]
        sc = None
        if center_row is not None:
            sc = a[center_row]
        for j in range(w):
            p2j = 2 ** j
            k = 0 if sc is None else sc[j]
            if p2j & sel_cols:
                k += (keys[j] * p12 + keys2[j]) * 32
                cols.append((k, j))
            elif p2j & sel_cols2:
                k += (keys2[j] * p12 + keys[j]) * 32
                cols2.append((k, j))
        cols.sort()
        cols2.sort()
        for j in range(len(cols)):
            if cols[j][0] != cols2[j][0]:
                return False
        if center_row is not None:
            sc = a[center_row]
            for j in range(len(cols)):
                if sc[cols[j][1]] != sc[cols2[j][1]]:
                    return False
        for i in range(len(rows)):
            ai = a[rows[i][1]]
            ai2 = a[rows2[i][1]]
            for j in range(len(cols)):
                if ai[cols[j][1]] != ai2[cols2[j][1]]:
                    return False
                if ai[cols2[j][1]] != ai2[cols[j][1]]:
                    return False

    return True


def solve():
    global row_keys, col_keys
    global ta

    if h == 1 or w == 1:
        if h == 1:
            a0 = a[0]
        else:
            a0 = ''.join(s)
        return check_sym1(a0)

    ta = [array.array('b') for _ in range(w)]
    for i in range(h):
        ai = a[i]
        for j in range(w):
            ta[j].append(ai[j])

    row_keys = {}
    col_keys = {}
    calc_row_keys()
    calc_col_keys()

    t0 = 2 ** h - 1
    if h % 2:
        for i in range(h):
            p2i = 2 ** i
            t = t0 - p2i
            for sel_rows in col_keys.keys():
                if sel_rows & p2i:
                    continue
                sel_rows2 = t - sel_rows
                if sel_rows2 < sel_rows:
                    continue
                if check_sym(sel_rows, sel_rows2, i):
                    return True
    else:
        for sel_rows in col_keys.keys():
            sel_rows2 = t0 - sel_rows
            if sel_rows2 < sel_rows:
                continue
            if check_sym(sel_rows, sel_rows2):
                return True

    return False


def main():
    global a, h, w

    h, w = input().split()
    h = int(h)
    w = int(w)
    a = []
    for _ in range(h):
        si = input()
        ai = array.array('b')
        ai.frombytes(si.encode())
        for j in range(w):
            ai[j] -= orda
        a.append(ai)

    print('YES' if solve() else 'NO')


if __name__ == '__main__':
    main()