Problem:


Score : 400 points

Problem Statement

We have an H-by-W matrix.
Let a_{ij} be the element at the i-th row from the top and j-th column from the left.
In this matrix, each a_{ij} is a lowercase English letter.

Snuke is creating another H-by-W matrix, A', by freely rearranging the elements in A.
Here, he wants to satisfy the following condition:

Every row and column in A' can be read as a palindrome.

Determine whether he can create a matrix satisfying the condition.

Note

A palindrome is a string that reads the same forward and backward.
For example, a, aa, abba and abcba are all palindromes, while ab, abab and abcda are not.

Constraints

1 ≤ H, W ≤ 100

a_{ij} is a lowercase English letter.

Input

Input is given from Standard Input in the following format:

H W
a_{11}a_{12}...a_{1W}
:
a_{H1}a_{H2}...a_{HW}

Output

If Snuke can create a matrix satisfying the condition, print Yes; otherwise, print No.

Sample Input 1

3 4
aabb
aabb
aacc

Sample Output 1

Yes

For example, the following matrix satisfies the condition.

abba
acca
abba

Sample Input 2

2 2
aa
bb

Sample Output 2

No

It is not possible to create a matrix satisfying the condition, no matter how we rearrange the elements in A.

Sample Input 3

5 1
t
w
e
e
t

Sample Output 3

Yes

For example, the following matrix satisfies the condition.

t
e
w
e
t

Sample Input 4

2 5
abxba
abyba

Sample Output 4

No

Sample Input 5

1 1
z

Sample Output 5

Yes



Sample input:
3 4
aabb
aabb
aacc


Sample output:
Yes

Submission status: Accepted

Solution code:
from collections import Counter
 
h, w = map(int, input().split())
a = Counter(''.join(input() for _ in range(h)))
 
center = h * w % 2 
side = (h//2) * (w%2) + (w//2) * (h%2)
corner = (h//2) * (w//2)

for _ in range(center):
    for i in a:
        if a[i] % 2 == 1:
            a[i] -= 1
            break
for _ in range(side):
    for j in a:
        if a[j] % 4 == 2:
            a[j] -= 2
            break

print('Yes' if sum(a[i]%4 for i in a) == 0 else 'No')

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

H, W = map(int, readline().split())
A = [readline().decode().rstrip() for _ in range(H)]

dicts = defaultdict(int)
for a in A:
    for c in a:
        dicts[c] += 1

g1 = H * W % 2
g2 = (H // 2) * (W % 2) + (W // 2) * (H % 2)
g4 = (H // 2) * (W // 2)

for _ in range(g1):
    for k, v in dicts.items():
        if (v % 4 == 1) | (v % 4 == 3):
            dicts[k] -= 1
            break

for _ in range(g2):
    for k, v in dicts.items():
        if v % 4 == 2:
            dicts[k] -= 2
            break
"""for _ in range(g4):
    for k, v in dicts.items():
        if (v % 4 == 0) & (v != 0):
            dicts[k] -= 4
            break
"""
for k, v in dicts.items():
    if v % 4 != 0:
        print('No')
        sys.exit()

print("Yes")

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
a = [input() for _ in range(h)]
alpha = [0]*26
for i in range(h):
    for j in range(w):
        alpha[ord(a[i][j])-ord("a")] += 1

ans = "Yes"
odd = 0
cnt = 0

for i in range(26):
    if alpha[i]%2 != 0:
        odd += 1
        alpha[i] -= 1
    if alpha[i]%4 != 0: cnt += 1

if odd > 1: ans = "No"
elif h%2 == 1 and w%2 == 1:
    if cnt > h//2+w//2: ans = "No"
elif h%2 == 1:
    if cnt > w//2: ans = "No"
elif w%2 == 1:
    if cnt > h/2: ans = "No"
else:
    if cnt > 0: ans = "No"
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

def main():
    H, W = map(int, input().split())
    a = ''
    for _ in range(H):
        a += input()
    
    nums1 = 0
    nums2 = 0
    if H % 2 != W % 2:
        nums2 -= 1
    for l in Counter(a).values():
        if l & 1:
            nums1 += 1
        if l % 4 > 1:
            nums2 += 1

    if nums1 > H*W % 2 or nums2 > (H%2) * ((W-1)//2) + (W%2) * ((H-1)//2):
        print('No')
    else:
        print('Yes')

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    H,W=MI()
    from collections import defaultdict
    dd = defaultdict(int)
    
    for i in range(H):
        a=input()
        for j in range(W):
            dd[a[j]]+=1
            
    L=[]
    for k,v in dd.items():
        L.append(v)
    
    four=0
    two=0
    one=0
    
    for aa in L:
        four+=aa//4
        bb=aa%4
        if bb==2 or bb==3:
            two+=1
        if bb==1 or bb==3:
            one+=1
        
    flag=0    
    if H%2==0 and W%2==0:
        if two==0 and one==0:
            flag=1
    elif H%2==0 and W%2!=0:
        if one==0 and two<=(H//2):
            flag=1
    elif H%2!=0 and W%2==0:
        if one==0 and two<=(W//2):
            flag=1
    else:
        if one<=1 and two<=((H+W)//2):
            flag=1
            
    if flag:
        print("Yes")
    else:
        print("No")
        
            
    
        

main()

Submission status: Accepted

Solution code:
from collections import defaultdict


def main():
    counter = defaultdict(int)
    H, W = list(map(int, input().split(' ')))
    for _ in range(H):
        A = input()
        for a in A:
            counter[a] += 1
    if H % 2 == W % 2 == 0:
        # 全ての個数が4の倍数ならOK
        for cnt in counter.values():
            if cnt % 4 != 0:
                print('No')
                return
        print('Yes')
    elif H % 2 == 0 and W % 2 == 1:
        non_quad_chars = 0
        for cnt in counter.values():
            if cnt % 4 == 1 or cnt % 4 == 3:
                print('No')
                return
            elif cnt % 4 == 2:
                non_quad_chars += 1
        if 2 * non_quad_chars <= H and (H - 2 * non_quad_chars) % 4 == 0:
            print('Yes')
        else:
            print('No')
    elif H % 2 == 1 and W % 2 == 0:
        non_quad_chars = 0
        for cnt in counter.values():
            if cnt % 4 == 1 or cnt % 4 == 3:
                print('No')
                return
            elif cnt % 4 == 2:
                non_quad_chars += 1
        if 2 * non_quad_chars <= W and (W - 2 * non_quad_chars) % 4 == 0:
            print('Yes')
        else:
            print('No')
    else:
        center_filled = False
        non_quad_chars = 0
        for cnt in counter.values():
            if cnt % 4 == 1 or cnt % 4 == 3:
                if center_filled:
                    print('No')
                    return
                center_filled = True
                if (cnt - 1) % 4 == 2:
                    non_quad_chars += 1
            elif cnt % 4 == 2:
                non_quad_chars += 1
        if 2 * non_quad_chars <= H + W - 2 and (H + W - 2 - 2 * non_quad_chars) % 4 == 0:
            print('Yes')
        else:
            print('No')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter

h, w = map(int, input().split())
a = Counter(''.join(input() for _ in range(h)))

center = h * w % 2
side = (h // 2) * (w % 2) + (w // 2) * (h % 2)

if sum(a[i] % 2 for i in a) != center:
    print('No')
    exit()
a = {i: a[i] - (a[i] % 2) for i in a}
cnt = sum(a[i] % 4 == 2 for i in a)
print('Yes' if cnt <= side else 'No')

Submission status: Accepted

Solution code:
from collections import Counter

h, w = map(int, input().split())
a = Counter(''.join(input() for _ in range(h)))

center = h * w % 2
side = (h // 2) * (w % 2) + (w // 2) * (h % 2)

if sum(a[i] % 2 for i in a) != center:
    print('No')
    exit()
a = {i: a[i] - (a[i] % 2) for i in a}
print('Yes' if sum(a[i] % 4 == 2 for i in a) <= side else 'No')

Submission status: Accepted

Solution code:
from collections import Counter

h, w = map(int, input().split())
a = Counter(''.join(input() for _ in range(h)))

center = h * w % 2
side = (h // 2) * (w % 2) + (w // 2) * (h % 2)

cnt = 0
for i in a:
    if a[i] % 2 == 1:
        a[i] -= 1
        cnt += 1
if cnt != center:
    print('No')
    exit()

print('Yes' if sum(a[i] % 4 == 2 for i in a) <= side else 'No')

Submission status: Accepted

Solution code:
from collections import Counter

h, w = map(int, input().split())
a = Counter(''.join(input() for _ in range(h)))

center = h * w % 2
side = (h // 2) * (w % 2) + (w // 2) * (h % 2)

cnt = 0
for i in a:
    if a[i] % 2 == 1:
        a[i] -= 1
        cnt += 1
if cnt != center:
    print('No')
    exit()

cnt = 0
for i in a:
    if a[i] % 4 == 2:
        a[i] -= 2
        cnt += 1
if cnt > side:
    print('No')
    exit()

print('Yes' if sum(a[i] % 4 for i in a) == 0 else 'No')

Submission status: Accepted

Solution code:
from collections import Counter

h, w = map(int, input().split())
a = Counter(''.join(input() for _ in range(h)))

center = h * w % 2
side = (h // 2) * (w % 2) + (w // 2) * (h % 2)

cnt = 0
for i in a:
    if a[i] % 2 == 1:
        a[i] -= 1
        cnt += 1
if cnt != center:
    print('No')
    exit()
cnt = 0
for i in a:
    if cnt == side:
        break
    if a[i] % 4 == 2:
        a[i] -= 2
        cnt += 1

print('Yes' if sum(a[i] % 4 for i in a) == 0 else 'No')

Submission status: Accepted

Solution code:
from collections import Counter

h, w = map(int, input().split())
a = Counter(''.join(input() for _ in range(h)))

center = h * w % 2
side = (h // 2) * (w % 2) + (w // 2) * (h % 2)

cnt = 0
for i in a:
    if cnt == center:
        break
    if a[i] % 2 == 1:
        a[i] -= 1
        cnt += 1
cnt = 0
for i in a:
    if cnt == side:
        break
    if a[i] % 4 == 2:
        a[i] -= 2
        cnt += 1

print('Yes' if sum(a[i] % 4 for i in a) == 0 else 'No')

Submission status: Accepted

Solution code:
from collections import Counter

h, w = map(int, input().split())
a = Counter(''.join(input() for _ in range(h)))

center = h * w % 2
side = (h // 2) * (w % 2) + (w // 2) * (h % 2)
corner = (h // 2) * (w // 2)

cnt = 0
for i in a:
    if cnt == center:
        break
    if a[i] % 2 == 1:
        a[i] -= 1
        cnt += 1
cnt = 0
for i in a:
    if cnt == side:
        break
    if a[i] % 4 == 2:
        a[i] -= 2
        cnt += 1

print('Yes' if sum(a[i] % 4 for i in a) == 0 else 'No')

Submission status: Accepted

Solution code:
from collections import Counter

h, w = map(int, input().split())
a = Counter(''.join(input() for _ in range(h)))

center = h * w % 2
side = (h // 2) * (w % 2) + (w // 2) * (h % 2)
corner = (h // 2) * (w // 2)

for i in range(center):
    for i in a:
        if a[i] % 2 == 1:
            a[i] -= 1
            break
for i in range(side):
    for i in a:
        if a[i] % 4 == 2:
            a[i] -= 2
            break

print('Yes' if sum(a[i] % 4 for i in a) == 0 else 'No')

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():
    H, W = in_nn()
    a = []
    for i in range(H):
        a += list(in_s())

    mH = -(-H // 2)
    mW = -(-W // 2)
    nums = defaultdict(int)
    for y in range(mH):
        for x in range(mW):
            if x == W - x - 1 and y == H - y - 1:
                n = 1
            elif x == W - x - 1:
                n = 2
            elif y == H - y - 1:
                n = 2
            else:
                n = 4
            nums[n] += 1

    count = Counter(a)
    td = defaultdict(int)
    for v in count.values():
        for n in (4, 2, 1):
            if v >= n:
                if td[n] < nums[n]:
                    c = min(v // n, nums[n] - td[n])
                    td[n] += c
                    v -= n * c

    # print(nums)
    # print(td)

    ans = 'Yes'
    for n in (4, 2, 1):
        if td[n] != nums[n]:
            ans = 'No'
            break

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter

def main():
    H, W = map(int, input().split())
    all_c = Counter([])
    for _ in range(H):
        line = list(input())
        line_c = Counter(line)
        all_c += line_c
    
    if H % 2 == 0 and W % 2 == 0:
        if all(val%4 == 0 for val in all_c.values()):
            print("Yes")
        else:
            print("No")

    elif H % 2 ^ W % 2:
        flag = all(val%2 == 0 for val in all_c.values())
        two_count = sum(val%4 == 2 for val in all_c.values())

        if H % 2 == 0:
            threshould = H//2
        else:
            threshould = W//2

        if flag and two_count <= threshould:
            print("Yes")
        else:
            print("No")

    elif H % 2 == 1 and W % 2 == 1:
        one_count = sum(val%2 == 1 for val in all_c.values())
        
        three_count = sum(val%4 == 3 for val in all_c.values())
        two_count = sum(val%4 == 2 for val in all_c.values())

        threshould = H//2 + W//2
        if one_count == 1 and three_count + two_count <= threshould:
            print("Yes")
        else:
            print("No")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w = list(map(int, input().split()))
a = []
for i in range(h):
    a.extend(list(input()))
    
from collections import Counter
c = Counter(a)
# print(c)
must = {1:0, 2:0, 4:0}
must[4] += (h//2) * (w//2)
if h%2==1:
    must[2] += (w//2)
if w%2==1:
    must[2] += (h//2)
if w%2==1 and h%2==1:
    must[1] += 1
    
for base in (4,2,1):
    val = 0
    for k,v in c.items():
        if val + v//base >= must[base]:
            c[k] -= (must[base] - val) * base
            val += (must[base] - val)
#             print(c, val, v, base)
            break
        val += v//base
        c[k] -= (v//base)*base
    if val<must[base]:
        ans = "No"
        break
else:
    ans = "Yes"
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

h, w = (int(x) for x in input().split())
A = []
for _ in range(h):
    A += list(input())

B = [0, 0, 0]
if h % 2 == 0 and w % 2 == 0:
    B[2] += h * w
elif h % 2 == 0 and w % 2 == 1:
    B[2] += h * (w - 1)
    B[1] += h
elif h % 2 == 1 and w % 2 == 0:
    B[2] += w * (h - 1)
    B[1] += w
else:
    B[2] += (w - 1) * (h - 1)
    B[1] += w + h - 2
    B[0] += 1

i = 0
for key, value in Counter(A).most_common():
    while value >= 4 and B[2] > 0:
        B[2] -= 4
        value -= 4
    while value >= 2 and B[1] > 0:
        B[1] -= 2
        value -= 2
    while value >= 1 and B[0] > 0:
        B[0] -= 1
        value -= 1
    if value != 0:
        print("No")
        exit()
else:
    print("Yes")
    exit()

Submission status: Accepted

Solution code:
from collections import Counter


def solve():
    YES, NO = "Yes", "No"
    if H % 2 and W % 2:
        if rems[1] == 0 and rems[3] == 1:
            rems[1] += 1
            rems[2] += 1
            rems[3] = 0
        if rems[1] != 1 or rems[3] or rems[2] > H // 2 + W // 2:
            return NO
        else:
            return YES
    elif H % 2 or W % 2:
        even_edge = H if W % 2 else W
        if rems[1] + rems[3] or rems[2] > even_edge // 2:
            return NO
        else:
            return YES
    else:
        if rems[1] + rems[2] + rems[3]:
            return NO
        else:
            return YES


H, W = map(int, input().split())
c = Counter()
for _ in range(H):
    c += Counter(input())
rems = Counter(v % 4 for v in c.values())
print(solve())

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
a,l=[list(input())for i in range(h)],[0]*26
for i in a:
 for j in i:l[ord(j)-97]+=1
o,t,f=(h//2)*(w//2),(h//2)*(w%2)+(w//2)*(h%2),(h%2)*(w%2)
for i in l:
 while o and i>3:o-=1;i-=4
 while t and i>1:t-=1;i-=2
 f-=i
print("Yes"if o==t==f==0else"No")

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
a=[input() for _ in range(h)]
d=dict()
for i in range(h):
    for j in range(w):
        if a[i][j] not in d:
            d[a[i][j]]=1
        else:
            d[a[i][j]]+=1
num=[]
for c in d:
    num.append(d[c])
num.sort(reverse=True)
ans=[[0]*w for _ in range(h)]
lis=[]
for i in range(h):
    for j in range(w):
        if ans[i][j]==0:
            if h-1-i==i and w-j-1!=j:
                ans[i][j]=1
                ans[i][w-1-j]=1
                lis.append(2)
            elif h-i-1!=i and w-j-1==j:
                ans[i][j]=1
                ans[h-1-i][j]=1
                lis.append(2)
            elif h-1-i==i and w-j-1==j:
                ans[i][j]=1
                lis.append(1)
            else:
                ans[i][j]=1
                ans[i][w-1-j]=1
                ans[h-1-i][j]=1
                ans[h-1-i][w-1-j]=1
                lis.append(4)
lis.sort(reverse=True)
for i in range(len(num)):
    for j in range(len(lis)):
        if num[i]>=lis[j]:
            num[i]-=lis[j]
            lis[j]=0
if sum(num)!=0 or sum(lis)!=0:
    print("No")
else:
    print("Yes")

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
a=[0]*h
book={}
for _ in range(h):
    a=input()
    for i in a:
        if i in book:
            book[i]+=1
        else:
            book[i]=1


if h%2==0 and w%2==0:
    for i in book:
        if book[i]%4!=0:
            print("No")
            exit()
    print("Yes")

elif h%2==1 and w%2==1:
    cnt=0
    odd=0
    for i in book:
        if book[i]%2==1:
            odd+=1
            if odd==2:
                print("No")
                exit()
        cnt+=book[i]//4
    if odd==0:
        print("No")
    else:
        if cnt>=(h-1)*(w-1)//4:
            print("Yes")
        else:
            print("No")
else:
    cnt=0
    for i in book:
        if book[i]%2==1:
            print("No")
            exit()
        cnt+=book[i]//4
    if h%2==1:
        if cnt>=(h-1)*w//4:
            print("Yes")
        else:
            print("No")
    else:
        if cnt>=(w-1)*h//4:
            print("Yes")
        else:
            print("No")

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
s = ""
cnt = [0] * 26
for _ in range(h):
    s = input()
    for i in range(len(s)):
        cnt[ord(s[i]) - ord("a")] += 1
#print(cnt)
c4=0
c2=0
c1=0
if h&1 == 1:
    c2 += w // 2
if w&1 == 1:
    c2 += h // 2
if (h&1 == 1) and (w&1 == 1):
    c1 = 1
c4 += (h//2) * (w//2)
#print(c1,c2,c4)

for i in range(26):
    if c4 <= 0:
        continue
    while cnt[i] >= 4:
        cnt[i] -= 4
        c4 -= 1
for i in range(26):
    if c2 <= 0:
        continue
    while cnt[i] >= 2:
        cnt[i] -= 2
        c2 -= 1
for i in range(26):
    if c1 <= 0:
        continue
    while cnt[i] % 4 == 1 or cnt[i] % 4 == 3:
        cnt[i] -= 1
        c1 -= 1

#print(c1,c2,c4)
if c1==0 and c2==0 and c4==0:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

h,w=MI()
lis=[]
for i in range(h):
    lis+=list(SI())
c=Counter(lis)
count1,count2=0,0
if h%2==0 and w%2==0:
    for x in c.keys():
        if c[x]%4!=0:
            print("No")
            sys.exit()
    print("Yes")
    
if h%2==0 and w%2==1:
    for x in c.keys():
        if c[x]%4==2:
            count2+=1
        elif c[x]%2==1:
            count1+=1
    if count2>h//2 or count1>0:
        print("No")
    else:
        print("Yes")
if w%2==0 and h%2==1:
    for x in c.keys():
        if c[x]%4==2:
            count2+=1
        elif c[x]%2==1:
            count1+=1
    #print(count1,count2)
    if count2>w//2 or count1>0:
        print("No")
    else:
        print("Yes")
if w%2==1 and h%2==1:
    for x in c.keys():
        if c[x]%4==2:
            count2+=1
        elif c[x]%2==1:
            count1+=1
    #print(count1,count2)
    if count1>1 or count2>h//2+w//2:
        print("No")
    else:
        print("Yes")

Submission status: Accepted

Solution code:
from collections import Counter
def check():
  H, W = map(int, input().split())
  S = [input() for _ in range(H)]
  s = ''.join(S)
  c = Counter(s)
  d = Counter(c.values())
  two = 0
  one = 0
  for k,v in d.items():
    if k%4==2 or k%4==3:
      two += 2*v
    if k%2==1:
      one += v
  if H%2==0 and W%2==0:
    if two>0 or one>0:
        return 'No'
  elif H%2==1 and W%2==1:
    if two>(H+W-2) or one>1:
      return 'No'
  elif H%2==1:
    if two>W or one>0:
      return 'No'
  elif W%2==1:
    if two>H or one>0:
      return 'No'
  return 'Yes'
print(check())

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
h,w = readInts()
S = ""
for i in range(h):
    S += input()
LIST = Counter(S)
#print(LIST)
if h%2 == 0 and w%2 == 0:
    for k,v in LIST.items():
        if v%4:
            print('No')
            exit()
elif (h%2 == 0 and w%2) or (h%2 and w%2 == 0):
    two = 0
    for k,v in LIST.items():
        if v%2 or v%4 == 3:
            print('No')
            exit()
        if v%4 == 2:
            two += 1
    if h%2 == 0:
        if two > h//2:
            print('No')
            exit()
    else:
        if two > w//2:
            print('No')
            exit()
else:
    odd = 0
    two = 0
    for k,v in LIST.items():
        if v%4 == 1:
            odd += 1
        if v%4 == 2:
            two += 1
        if v%4 == 3:
            print('No')
            exit()
    if odd != 1:
        print('No')
        exit()
    if two > ((h-1)//2 + (w-1)//2):
        print('No')
        exit()
print('Yes')

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
A = [list(str(input())) for _ in range(h)]

#A = [list('a'*100) for _ in range(h)]

idx = 0
d = {}
C = [0]*26
for i in range(h):
    for j in range(w):
        C[ord(A[i][j])-ord('a')] += 1
        d[(i, j)] = idx
        idx += 1

def Find(x, par):
    if par[x] < 0:
        return x
    else:
        par[x] = Find(par[x], par)
        return par[x]

def Unite(x, y, par, rank):
    x = Find(x, par)
    y = Find(y, par)

    if x != y:
        if rank[x] < rank[y]:
            par[y] += par[x]
            par[x] = y
        else:
            par[x] += par[y]
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

def Same(x, y, par):
    return Find(x, par) == Find(y, par)

def Size(x, par):
    return -par[Find(x, par)]

n = h*w
par = [-1]*n
rank = [0]*n

for i in range(h):
    for j in range(w):
        p = d[(i, j)]
        q = d[(i, w-1-j)]
        Unite(p, q, par, rank)
        q = d[(h-1-i, j)]
        Unite(p, q, par, rank)

S = []
for i in range(n):
    if par[i] < 0:
        S.append(-par[i])
S.sort(reverse=True)
#print(S)
#print(len(S))
#print(C)

C = [-c for c in C]
import heapq
heapq.heapify(C)
for s in S:
    c = -heapq.heappop(C)
    if c >= s:
        c -= s
        heapq.heappush(C, -c)
    else:
        print('No')
        exit()
else:
    print('Yes')

Submission status: Accepted

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

import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
from heapq import _heapify_max, _heappop_max, _siftdown_max
from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)



def main():
    Num = Union[int, float]
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def isp():   return input().split()
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    def _heappush_max(heap, item):
        heap.append(item)
        _siftdown_max(heap, 0, len(heap)-1)

    
    def check(hp, mul4, mul2, mul1):
        while hp:
            if mul4:
                top = _heappop_max(hp)
                if top < 4:
                    return False
                top -= 4
                mul4 -= 1
                if top:
                    _heappush_max(hp, top)
            elif mul2:
                top = _heappop_max(hp)
                if top < 2:
                    return False
                top -= 2
                mul2 -= 1
                if top:
                    _heappush_max(hp, top)
            elif mul1:
                top = _heappop_max(hp)
                if top < 1:
                    return False
                top -= 1
                mul1 -= 1
                if top:
                    _heappush_max(hp, top)
            else:
                raise RuntimeError
        return True

    
    h, w = mi()
    c = Counter()
    for _ in range(h):
        c += Counter(input())
    hp = list(c.values())
    _heapify_max(hp)
    
    if h % 2 == 0 and w % 2 == 0:
        mul4, mul2, mul1 = h * w // 4, 0, 0
    elif h % 2 == 0:
        mul4, mul2, mul1 = h * (w-1) // 4, h//2, 0
    elif w % 2 == 0:
        mul4, mul2, mul1 = (h-1) * w //4, w//2, 0
    else:
        mul2, mul1 = (h-1)//2 + (w-1)//2, 1
        mul4 = (h * w - mul2 * 2 + mul1) // 4
    
    print('Yes') if check(hp, mul4, mul2, mul1) else print('No')

    


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter
import sys

h, w = map(int, input().split())
arr = [list(map(str, input().rstrip())) for _ in range(h)]

arr = sum(arr, [])

c = Counter(arr)
c = list(c.values())

if h % 2 == 0 and w % 2 == 0:
    ans = all([x % 4 == 0 for x in c])

elif h % 2 == 1 and w % 2 == 1:
    even = (h + w) // 2 - 1
    odd_cnt = len([x for x in c if x % 2 == 1])
    if odd_cnt != 1:
        print("No")
        sys.exit()
    odd = sum([x for x in c if x % 2 == 1])
    if odd % 4 == 3:
        even -= 1
    c.remove(odd)
    ans = True if sum([x % 4 == 2 for x in c]) <= even else False
    ans &= all([x % 4 == 0 for x in c if x % 4 != 2])

else:
    even = h // 2 if h % 2 == 0 else w // 2
    ans = True if sum([x % 4 == 2 for x in c]) <= even else False
    ans &= all([x % 4 == 0 for x in c if x % 4 != 2])

print("Yes" if ans else "No")