Problem:


Score : 700 points

Problem Statement

We have a string s consisting of lowercase English letters.
Snuke is partitioning s into some number of non-empty substrings.
Let the subtrings obtained be s_1, s_2, ..., s_N from left to right. (Here, s = s_1 + s_2 + ... + s_N holds.)
Snuke wants to satisfy the following condition:

For each i (1 \leq i \leq N), it is possible to permute the characters in s_i and obtain a palindrome.

Find the minimum possible value of N when the partition satisfies the condition.

Constraints

1 \leq |s| \leq 2 \times 10^5

s consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

s

Output

Print the minimum possible value of N when the partition satisfies the condition.

Sample Input 1

aabxyyzz

Sample Output 1

2

The solution is to partition s as aabxyyzz = aab + xyyzz.
Here, aab can be permuted to form a palindrome aba, and xyyzz can be permuted to form a palindrome zyxyz.

Sample Input 2

byebye

Sample Output 2

1

byebye can be permuted to form a palindrome byeeyb.

Sample Input 3

abcdefghijklmnopqrstuvwxyz

Sample Output 3

26

Sample Input 4

abcabcxabcx

Sample Output 4

3

The solution is to partition s as abcabcxabcx = a + b + cabcxabcx.



Sample input:
aabxyyzz


Sample output:
2

Submission status: Wrong Answer

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


s = input()
n = len(s)
from collections import Counter
c = Counter(s)
e = [0]*n # 奇数回数の文字の最後の出現位置
for i,item in enumerate(s):
    if c[item]%2==1:# and d[item]==c[item]:
        e[i] = 1
        
ans = 0
val = 0
d = {k:0 for k in c.keys()}
for i,item in enumerate(s):
    d[item] += 1
#     if d[item]%2==1:
        
    if val+e[i]>=2:
        ans += 1
        val = 1
    else:
        val += e[i]
print(ans+1)

Submission status: Wrong Answer

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


s = input()
n = len(s)
from collections import Counter
c = Counter(s)
ans = sum(v%2==1 for v in c.values())
print(ans)
# d = {k:0 for k in c.keys()}
# e = [0]*n # 奇数回数の文字の最後の出現位置
# e2 = [0]*n
# for i,item in enumerate(s):
#     d[item] += 1
#     if d[item]%2==1:
#         e2[i] = 1
#     else:
#         e2[i] = -1
#     if c[item]%2==1 and d[item]==c[item]:
#         e[i] = 1
        
# ans = 0
# val = 0
# for i in range(n):
#     if val+e[i]>=2:
#         ans += 1
#         val = 1
#     else:
#         val += e[i]
# print(ans+1)

Submission status: Wrong Answer

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


s = input()
n = len(s)
from collections import Counter
c = Counter(s)
d = {k:0 for k in c.keys()}
e = [0]*n # 奇数回数の文字の最後の出現位置
for i,item in enumerate(s):
    d[item] += 1
    if c[item]%2==1 and d[item]==c[item]:
        e[i] = 1
        
ans = 0
val = 0
for i in range(n):
    if val+e[i]>=2:
        ans += 1
        val = 1
    else:
        val += e[i]
print(ans+1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
S = list(input())[: -1]
N = len(S)
cs = [0] * (N + 1)
a = ord("a")
table = [1 << x for x in range(27)]
for i in range(N):
  cs[i + 1] = cs[i] ^ table[(ord(S[i]) - a)]
d = dd(lambda: N + 1)

dp = [N] * (N + 1)
dp[0] = 0
d[0] = 0
for i in range(N):
  for j in range(26):
    x = d[cs[i + 1] ^ table[j]]
    #print(cs[i + 1], table[j], d[x])
    if x >= N + 1: continue
    dp[i + 1] = min(dp[i + 1], dp[x] + 1)
  x = d[cs[i + 1]]
  if x <= N: dp[i + 1] = min(dp[i + 1], dp[x] + 1)
  d[cs[i + 1]] = min(x, dp[i + 1])
print(dp[-1])

Submission status: Wrong Answer

Solution code:
import sys
import heapq
hpush = heapq.heappush
hpop = heapq.heappop
from collections import defaultdict as dd
input = sys.stdin.readline
S = list(input())[: -1]
N = len(S)
cs = [0] * (N + 1)
a = ord("a")
table = [1 << x for x in range(27)]
for i in range(N):
  cs[i + 1] = cs[i] ^ table[(ord(S[i]) - a)]
#print(cs)
d = dd(list)
for i in range(N, -1, -1): d[cs[i]].append(i)
#print(d)

dist = [N] * (N + 1)
vis = [0] * (N + 1)
dist[0] = 0
h = [0]
while len(h):
  v = hpop(h)
  v1 = v % (10 ** 6)
  v0 = v // (10 ** 6)
  if vis[v1]: continue
  vis[v1] = 1
  for i in range(26):
    for x in d[cs[v1] ^ table[i]]:
      if dist[x] > dist[v1] + 1:
        dist[x] = dist[v1] + 1
        hpush(h, dist[x] * (10 ** 6) + x)
    while len(d[cs[v1] ^ table[i]]):
      if d[cs[v1] ^ table[i]][-1] <= v1: d[cs[v1] ^ table[i]].pop()
      else: break
  for x in d[cs[v1]]:
    if dist[x] > dist[v1] + 1:
      dist[x] = dist[v1] + 1
      hpush(h, dist[x] * (10 ** 6) + x)
  while len(d[cs[v1]]):
    if d[cs[v1]][-1] <= v1: d[cs[v1]].pop()
    else: break
print(dist[-1])

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
S = list(input())[: -1]
N = len(S)
cs = [0] * (N + 1)
a = ord("a")
table = [1 << x for x in range(27)]
for i in range(N):
  cs[i + 1] = cs[i] ^ table[(ord(S[i]) - a)]
#print(cs)
d = dd(set)
for i in range(N, -1, -1): d[cs[i]].add(i)

dp = [N] * (N + 1)
dp[0] = 0
for i in range(N):
  for j in range(26):
    cp = set(d[cs[i] ^ table[j]])
    for k in cp:
      dp[k] = min(dp[k], dp[i] + 1)
      d[cs[i] ^ table[j]].discard(k)
  cp = set(d[cs[i]])
  for k in cp:
    if i != k:
      dp[k] = min(dp[k], dp[i] + 1)
      d[cs[i]].discard(k)
print(dp[-1])

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
S = list(input())[: -1]
N = len(S)
cs = [0] * (N + 1)
a = ord("a")
for i in range(N):
  cs[i + 1] = cs[i] ^ (1 << (ord(S[i]) - a))
#print(cs)
d = dd(lambda: N + 1)
for i in range(N, -1, -1): d[cs[i]] = i

x = N
res = 0
while x:
  y = x - 1
  for i in range(26): y = min(y, d[cs[x] ^ (1 << i)])
  y = min(y, d[cs[x]])
  x = y
  res += 1
print(res)

Submission status: Wrong Answer

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

S = list(input().rstrip())
INF = 10**15

bit = 0
dic = {0 : 0}
for ind, s in enumerate(S):
    bit ^= 1<<(ord(s)-97)
    score = INF
    if bit in dic:
        if ind != len(S)-1:
            continue
        else:
            score = dic[bit] + 1
    for i in range(26):
        nbit = bit^(1<<i)
        if nbit in dic and dic[nbit]+1 < score:
            score = dic[nbit]+1
    dic[bit] = score

print(dic[bit])

Submission status: Wrong Answer

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

S = list(input().rstrip())
INF = 10**15

bit = 0
dic = {0 : 0}
for i, s in enumerate(S):
    bit ^= 1<<(ord(s)-97)
    if bit in dic: continue
    score = INF
    for i in range(26):
        nbit = bit^(1<<i)
        if nbit in dic and dic[nbit]+1 < score:
            score = dic[nbit]+1
    dic[bit] = score

print(max(dic[bit], 1))

Submission status: Wrong Answer

Solution code:
def main():
    S = input()
    n = len(S)
    a = {j: i for i, j in enumerate('abcdefghijklmnopqrstuvwxyz')}
    S = [a[i] for i in S]
    dp = [10**9]*(n+1)
    dp[0] = 0

    parity = 0
    dict_parity = {0: 0}

    for i, s in enumerate(S):
        parity ^= 2**s
        ans = i+1
        if parity in dict_parity:
            ans = min(ans, dp[dict_parity[parity]]+1)
        for j in range(26):
            parity2 = parity ^ 2**j
            if parity2 in dict_parity:
                ans = min(ans, dp[dict_parity[parity2]]+1)
        dp[i+1] = ans
        if parity not in dict_parity:
            dict_parity[parity] = ans
        elif dp[dict_parity[parity]] > ans:
            dict_parity[parity] = i+1
    print(dp[-1])


main()

Submission status: Wrong Answer

Solution code:
def main():
    S = input()
    n = len(S)
    a = {j: i for i, j in enumerate('abcdefghijklmnopqrstuvwxyz')}
    S = [a[i] for i in S]
    dp = [10**9]*(n+1)
    dp[0] = 0

    parity = 0
    dict_parity = {0: 0}

    for i, s in enumerate(S):
        parity ^= 2**s
        ans = i+1
        if parity in dict_parity:
            ans = min(ans, dp[dict_parity[parity]]+1)
        for j in range(26):
            parity2 = parity ^ 2**j
            if parity2 in dict_parity:
                ans = min(ans, dp[dict_parity[parity2]]+1)
        dp[i+1] = ans
        if parity not in dict_parity:
            dict_parity[parity] = ans
        elif dict_parity[parity] > ans:
            dict_parity[parity] = i+1
    print(dp[-1])


main()

Submission status: Wrong Answer

Solution code:
def main():
    S = input()
    n = len(S)
    a = {j: i for i, j in enumerate('abcdefghijklmnopqrstuvwxyz')}
    S = [a[i] for i in S]
    dp = [10**9]*(n+1)
    dp[0] = 0

    parity = 0
    dict_parity = {0: 0}

    for i, s in enumerate(S):
        parity ^= 2**s
        ans = i+1
        if parity not in dict_parity:
            dict_parity[parity] = i+1
        else:
            ans = min(ans, dp[dict_parity[parity]]+1)
        for j in range(26):
            parity2 = parity ^ 2**j
            if parity2 in dict_parity:
                ans = min(ans, dp[dict_parity[parity2]]+1)
        dp[i+1] = ans
        if dp[dict_parity[parity]] > ans:
            dict_parity[parity]
    print(dp[-1])


main()

Submission status: Wrong Answer

Solution code:
def main():
    S = input()
    n = len(S)
    a = {j: i for i, j in enumerate('abcdefghijklmnopqrstuvwxyz')}
    S = [a[i] for i in S]
    dp = [10**9]*(n+1)
    dp[0] = 0

    parity = 0
    dict_parity = {0: 0}

    for i, s in enumerate(S):
        parity ^= 2**s
        ans = i+1
        if parity not in dict_parity:
            dict_parity[parity] = i+1
        else:
            ans = min(ans, dp[dict_parity[parity]]+1)
        for j in range(26):
            parity2 = parity ^ 2**j
            if parity2 in dict_parity:
                ans = min(ans, dp[dict_parity[parity2]]+1)
        dp[i+1] = ans
    print(dp[-1])


main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
s = input()
n = len(s)
dp = defaultdict(int)
dp[0] = 1
ls = [1<<(ord(s[0])-97)]
for i in range(1,n):
  ls.append(ls[-1]^(1<<(ord(s[i])-97)))
for i in range(n):
  for b in range(26):
    bit = 1<<b
    if dp[ls[i]^bit] == 0:
      continue
    if dp[ls[i]] == 0:
      dp[ls[i]] = dp[ls[i]^bit]+1
    else:
      dp[ls[i]] = min(dp[ls[i]^bit]+1,dp[ls[i]])
print(dp[ls[n-1]]-1)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

    S = input().rstrip('\n')
    N = len(S)

    A = [ord(s)-97 for s in S]
    H = [0] * (N+1)
    h2i = defaultdict(list)
    for i in range(N):
        H[i+1] = H[i] ^ (1 << A[i])
        h2i[H[i+1]].append(i+1)

    dp = [N+1] * (N+1)
    dp[0] = 0
    for i in range(N):
        h = H[i]
        if i == 0:
            if h2i[h]:
                for ii in h2i[h]:
                    dp[ii] = 1
        for j in range(26):
            new_h = h ^ (1 << j)
            if h2i[new_h]:
                ii = h2i[new_h][-1]
                if ii > i:
                    dp[ii] = min(dp[ii], dp[i] + 1)
    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

    S = input().rstrip('\n')
    N = len(S)

    A = [ord(s)-97 for s in S]
    H = [0] * (N+1)
    h2i = defaultdict(list)
    for i in range(N):
        H[i+1] = H[i] ^ (1 << A[i])
        h2i[H[i+1]].append(i+1)

    dp = [N+1] * (N+1)
    dp[0] = 0
    for i in range(N):
        h = H[i]
        if h2i[h]:
            ii = h2i[h][-1]
            if ii > i:
                dp[ii] = min(dp[ii], max(1, dp[i]))
        for j in range(26):
            new_h = h ^ (1 << j)
            if h2i[new_h]:
                ii = h2i[new_h][-1]
                if ii > i:
                    dp[ii] = min(dp[ii], dp[i] + 1)
    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
inf = 10**6
s = input()
N = len(s)
cumsum = [0]*(N+1)
d = defaultdict(lambda :-1)
for i in range(N):
    num = ord(s[i])-ord('a')
    cumsum[i] = cumsum[i-1]^(1<<num)
    d[cumsum[i]] = i
dp = [inf]*(N+1)
dp[-2] = 0
for i in range(N-2, -2, -1):
    j = d[cumsum[i]]
    if j>i:
        dp[i] = dp[j]+1
    for k in range(26):
        x = cumsum[i]+(1<<k)
        j = d[x]
        if j>i:
            dp[i] = min(dp[i], dp[j]+1)
print(dp[-1])

Submission status: Wrong Answer

Solution code:
S = input()
N = len(S)

def ctoi(c):
    return ord(c) - ord('a')

cums = [0]
for c in S:
    cums.append(cums[-1] ^ (1<<ctoi(c)))
if cums[-1] == 0:
    print(1)
    exit()

dp = {0:0}
for b in cums:
    if b in dp: continue
    for k in range(26):
        if b&(1<<k)==0: continue
        msk = b^(1<<k)
        if msk in dp:
            if b in dp:
                dp[b] = min(dp[b], dp[msk]+1)
            else:
                dp[b] = dp[msk]+1
last = cums[-1]
print(dp[last] if last in dp else N)

Submission status: Wrong Answer

Solution code:
S = input()
N = len(S)

def ctoi(c):
    return ord(c) - ord('a')

cums = [0]
for c in S:
    cums.append(cums[-1] ^ (1<<ctoi(c)))

dp = [N] * (N+1)
dp[0] = 1
idxs = {0:0}
for i,b in enumerate(cums):
    if b in idxs:
        dp[i] = dp[idxs[b]]
        continue
    idxs[b] = i
    dp[i] = dp[i-1] + 1
    cnt = 0
    for k in range(26):
        if b&(1<<k)==0: continue
        cnt += 1
        msk = b^(1<<k)
        if msk in idxs:
            dp[i] = min(dp[i], dp[idxs[msk]]+1)
    if cnt <= 1: dp[i] = 1
print(dp[-1])

Submission status: Wrong Answer

Solution code:
import sys

s = input()
end = len(s)-1

last = [-1] * 2

dic = {}
alp = "abcdefghijklmnopqrstuvwxyz"
for i in alp:
    dic[i] = 0

ans = 0
alp = "abcdefghijklmnopqrstuvwxyz"

while True:

    dic = {}
    last = [-1] * 2
    for i in alp:
        dic[i] = 0

    t = "".join(reversed(list(s)))
    
    for i in range(len(s)):
    
        dic[s[i]] ^= 1

        ns = 0
        for j in dic:
            ns += dic[j]

        if ns < 2:
            last[ns] = i

    
    s = s[max(last)+1:]
    


    dic = {}
    last = [-1] * 2
    for i in alp:
        dic[i] = 0
    
    for i in range(len(t)):

        dic[t[i]] ^= 1

        ns = 0
        for j in dic:
            ns += dic[j]

        if ns < 2:
            last[ns] = i

    
    t = t[max(last)+1:]

    t = "".join(reversed(list(t)))
    #print (s,t)

    if len(s) > len(t):
        s = t

    if len(s) == 0:
        print (ans+1)
        sys.exit()
    else:
        ans += 1

Submission status: Wrong Answer

Solution code:
import sys

s = input()

last = [-1] * (len(s)+2)

dic = {}
alp = "abcdefghijklmnopqrstuvwxyz"
for i in alp:
    dic[i] = 0

for i in range(len(s)):

    dic[s[i]] ^= 1

    ns = 0
    for j in dic:
        ns += dic[j]

    last[ns] = i

for i in range(len(s)+1):

    if last[i+1] < last[i]:
        print (max(1,i))
        sys.exit()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

s = input()
N = len(s)

# ord('a') == 97
acc_xor = [0] * (N+1)
for i in range(N):
    acc_xor[i+1] = acc_xor[i] ^ (2 ** (ord(s[i]) - 97))
acc2idx = defaultdict(lambda: [0])
for i in range(N+1):
    acc2idx[acc_xor[i]].append(i)

for k in acc2idx.keys():
    acc2idx[k] = [max(acc2idx[k])]

dp = [defaultdict(lambda: float('inf')) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    hash_cur = acc_xor[i]
    dp[acc2idx[hash_cur][0]][hash_cur] = min(dp[acc2idx[hash_cur][0]][hash_cur], dp[i][hash_cur] + 1)
    for j in range(26):
        hash_new = hash_cur ^ (2**j)
        dp[acc2idx[hash_new][0]][hash_new] = min(dp[acc2idx[hash_new][0]][hash_new], dp[i][hash_cur] + 1)

print(min(dp[-1].values()))

Submission status: Wrong Answer

Solution code:
s = input()
n = len(s)
s = [ord(c)-ord('a') for c in s]
h = [0] * n
h[0] = 1<<s[0]
for i in range(1,n):
  h[i] = h[i-1] ^ (1<<s[i])
dp = [0] * (n)
for i in range(1,n):
  syo = float("inf")
  for j in range(0,i):
    tmp = h[i] ^ h[j]
    if tmp == 0 or (tmp & (tmp-1)) == 0:
      syo = min(syo,dp[j]+1)
  dp[i] = syo
print(dp[-1])

Submission status: Wrong Answer

Solution code:
s = input()

L = [[0]*26]
for c in s:
    LL = L[-1].copy()
    LL[ord(c)-97] += 1
    L.append(LL)

def solve(left, right):
    cnt = 0
    U = set()
    res = 0
    for i, (b, a) in enumerate(zip(L[right], L[left])):
        if b-a == 1:
            U.add(i)
    f = 0
    l = left
    for i in range(left, right):
        if ord(s[i])-97 in U:
            f += 1
        else:
            if f >= 2:
                res += solve(l, i-f)
                res += f
                l = i
            f = 0
    if l != left:
        res += solve(l, right)
    else:
        for b, a in zip(L[right], L[left]):
            if (b - a) % 2 == 1:
                res += 1
    return res

print(max(solve(0, len(s)),1))

Submission status: Wrong Answer

Solution code:

s = input()
L = [0]*26
for c in s:
    L[ord(c)-97] += 1
cnt = 0
for l in L:
    if l%2==1:
        cnt += 1
print(max(cnt,1))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

S = input()
num = [0]*26

for s in S:
	num[ord(s)-97] += 1

tmp = 0
for n in num:
	if n%2 == 1:
		tmp += 1

print(max(tmp,1))

Submission status: Wrong Answer

Solution code:
import string

ALPHABETS = string.ascii_lowercase

s = input()
N = len(s)
MAX = 2 * 10 ** 5
a = [0] * (N + 1)
for i, c in enumerate(s):
    idx = ALPHABETS.index(c)
    a[i+1] = a[i] ^ (2 ** idx)

opt = [0] * (N + 1)
dp = {}
dp[0] = 0
for i in range(1, N + 1):
    dp[a[i]] = min(dp.get(a[i], MAX), min([dp.get(a[i] ^ 2 ** j, MAX) if not j == -1 else dp.get(a[i] ^ 0, MAX) for j in range(-1, 26)]) + 1)

print(dp[a[N]])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3

import sys
import itertools

s = next(sys.stdin).rstrip()
n = len(s)
a = 0
# b = [0 for i in range(n + 1)]
succ = [[] for i in range(n)]
d = {0: [0]}
for i, c in enumerate(s):
    ac = ord(c) - 0x61
    br = 1 << ac
    a = a ^ br
    # b[i + 1] = a
    # print("i = {}, a = {:08X}".format(i, a))
    if a not in d:
        d[a] = []
    d[a].append(i + 1)
    for alt in itertools.chain([1 << rot for rot in range(26)], [0]):
        x = a ^ alt
        if x in d:
            # print("x, d[x]", x, d[x])
            for j in d[x]:
                if j < i + 1:
                    succ[j].append(i + 1)

reached = [None for i in range(n + 1)]
reached[n] = 0

def path(i, max_):
    if reached[i] is not None:
        return reached[i] if max_ is None or reached[i] <= max_ else None
    ret = None
    for j in reversed(succ[i]):
        newmax = None if max_ is None else max_ - 1
        c = path(j, newmax)
        if c is not None:
            ret = c + 1
            max_ = ret - 1  # == c
    if ret is not None:
        reached[i] = ret
    return ret


def pathNR(i, max_):
    dict = { 'remain': succ[i], 'pos': i, 'max': max_, 'ret': None }
    stack = []

    def one_better(v, w):
        if v is None:   return False
        elif w is None: return True
        else:           return v + 1 < w

    def updateRet(v):
        if one_better(v, dict['ret']):
            dict['ret'] = v + 1
            dict['max'] = dict['ret'] - 1  # == v

    while True:
        if dict['remain']:
            j = dict['remain'].pop()
            if reached[j] is not None:
                updateRet(reached[j])
            else:
                stack.append(dict)
                dict = { 'remain': succ[j], 'pos': j,
                         'max': None if dict['max'] is None
                                     else dict['max'] - 1,
                         'ret': None }
        else:
            pRet = dict['ret']
            if stack:
                dict = stack.pop()
                updateRet(pRet)
            else:
                return pRet

# for i in range(len(succ)):
    # print(i, succ[i])

x = pathNR(0, None)
print(x)

Submission status: Wrong Answer

Solution code:
import string

ALPHABETS = string.ascii_lowercase
ALPHABETS_TO_INT = {}

for pos, c in enumerate(ALPHABETS):
    ALPHABETS_TO_INT[c] = pos
count = 1


def check(s):
    global count
    if is_available(s):
        return
    for i in range(1, len(s)):
        if is_available(s[i:]):
            count += 1
            # print(s[:i])
            check(s[:i])
            return
        elif is_available(s[:len(s)-i]):
            count += 1
            # print(s[len(s)-i:])
            check(s[len(s)-i:])
            return


def is_available(s):
    num_arr = [False] * 26
    for c in s:
        num_arr[ALPHABETS_TO_INT[c]] = not num_arr[ALPHABETS_TO_INT[c]]
    if num_arr.count(True) <= 1:
        return True
    return False


s = input()
check(s)
print(count)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    a = [2**(ord(c)-97) for c in S()]
    b = [0]
    d2 = {}
    c = 0
    ii = [2**i for i in range(26)]
    for t,i in zip(a, range(1,len(a)+1)):
        c ^= t
        tr = inf
        if c in d2:
            tr = d2[c] + 1

        for j in ii:
            e = c ^ j
            if e in d2 and d2[e] + 1 < tr:
                tr = d2[e] + 1
        if c not in d2 or d2[c] > tr:
            d2[c] = tr
    return d2[c]



print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    a = [2**(ord(c)-97) for c in S()]
    b = [0]
    d2 = {}
    c = 0
    ii = [2**i for i in range(26)]
    for t,i in zip(a, range(1,len(a)+1)):
        c ^= t
        tr = inf
        if c in d2:
            if c == 0:
                tr = 1
            else:
                tr = d2[c] + 1

        for j in ii:
            e = c ^ j
            if e == 0:
                tr = 1
                break
            if e in d2 and d2[e] + 1 < tr:
                tr = d2[e] + 1
        if c not in d2 or d2[c] > tr:
            d2[c] = tr
    return d2[c]



print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    a = [2**(ord(c)-97) for c in S()]
    b = [0]
    d = {}
    d[0] = 0
    c = 0
    ii = [2**i for i in range(26)]
    for t,i in zip(a, range(1,len(a)+1)):
        c ^= t
        tr = inf
        if c in d:
            if c == 0:
                tr = 1
            tr = b[d[c] - 1] + 1
        else:
            d[c] = i

        for j in ii:
            e = c ^ j
            if e == 0:
                tr = 1
                break
            if e in d and b[d[e]] + 1 < tr:
                tr = b[d[e]] + 1
        b.append(tr)
        if b[d[c]] > tr:
            b[d[c]] = tr
    return b[-1]



print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    a = [2**(ord(c)-97) for c in S()]
    b = [0]
    d = {}
    d[0] = 0
    c = 0
    ii = [2**i for i in range(26)]
    for t,i in zip(a, range(1,len(a)+1)):
        c ^= t
        tr = inf
        if c in d:
            if c == 0:
                b.append(1)
                continue
            tr = b[d[c] - 1] + 1
        else:
            d[c] = i

        for j in ii:
            e = c ^ j
            if e in d and b[d[e]] + 1 < tr:
                tr = b[d[e]] + 1
        b.append(tr)
    return b[-1]



print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    a = [2**(ord(c)-97) for c in S()]
    b = [0]
    d = {}
    d[0] = 0
    c = 0
    ii = [2**i for i in range(26)]
    for t,i in zip(a, range(1,len(a)+1)):
        c ^= t
        tr = inf
        if c in d:
            tr = b[d[c]] + 1
        else:
            d[c] = i

        for j in ii:
            e = c ^ j
            if e in d and b[d[e]] + 1 < tr:
                tr = b[d[e]] + 1
        b.append(tr)
    return b[-1]



print(main())

Submission status: Wrong Answer

Solution code:
a, opt = [0], [0]
data = input()
tmp = 0b0

for i,item in enumerate(data):
    tmp = tmp ^ 2**(ord(item) - 96)
    a.append(tmp)
    min_num = ""
    for j in range(i+1):
        hoge = a[i+1] ^ a[j]
        if (hoge == 0 or hoge & (hoge-1) == 0):
            if min_num == "":
                min_num = opt[j]
            elif opt[j] < min_num:
                min_num = opt[j]
    opt.append(min_num + 1)
print(opt)

Submission status: Wrong Answer

Solution code:
s = input()
cnt = [0] * 26
for ch in s:
    cnt[ord(ch) - ord('a')] += 1
res = 0
for x in cnt:
    res += x & 1
print(res if res else res + 1)

Submission status: Wrong Answer

Solution code:
s = input()
n = len(s)
cA = ord('a')
P = {0: -1}
cur = 0

dp = [10**18]*(n+1)
dp[-1] = 0

for i in range(n):
    c = ord(s[i]) - cA
    dp[i] = dp[i-1] + 1
    cur ^= 1 << c
    # even
    if cur in P:
        dp[i] = min(dp[i], P[cur] + 1)
    # odd
    for k in range(26):
        need = cur ^ (1 << k)
        if need in P:
            dp[i] = min(dp[i], P[need] + 1)
    P[cur] = min(P.get(cur, 10**18), dp[i])
print(dp[n-1])

Submission status: Wrong Answer

Solution code:
s = input()
n = len(s)
cA = ord('a')
P = {0: -1}
cur = 0

dp = [10**18]*(n+1)
dp[-1] = 0

for i in range(n):
    c = ord(s[i]) - cA
    dp[i] = dp[i-1] + 1
    cur ^= 1 << c
    # even
    if cur in P:
        j = P[cur]
        dp[i] = min(dp[i], dp[j] + 1)
    # odd
    for k in range(26):
        need = cur ^ (1 << k)
        if need in P:
            j = P[need]
            dp[i] = min(dp[i], dp[j] + 1)
    if cur not in P:
        P[cur] = i
print(dp[n-1])

Submission status: Wrong Answer

Solution code:
s = raw_input()

root = {
  'parent': None,
  'child': {},
  'odds': 0
}

i = 0
for c in s:
  i += 1
  nodes = [root]
  while nodes:
    nex = []
    for d in nodes:
      d[c] = d.get(c, 0) + 1
      d['odds'] += 1 if d[c] % 2 == 1 else -1
      if d['odds'] == 0 and d['parent']:
        del d['parent']['child'][d['no']]
        continue
      nex += d['child'].values()
      if d['odds'] <= 1:
        d['child'][i] = { 'parent': d, 'no': i, 'child': {}, 'odds': 0 }
    nodes = nex

ans = 1
nodes = [root]
while nodes:
  nex = []
  for n in nodes:
    if n['odds'] <= 1:
      print ans
      exit()
    nex += n['child'].values()
  nodes = nex
  ans += 1
print "error"

Submission status: Wrong Answer

Solution code:
a=list(raw_input())
alp={"a":0,"b":0,"c":0,"d":0,"e":0,"f":0,"g":0,"h":0,"i":0,"j":0,"k":0,"l":0,"m":0,"n":0,"o":0,"p":0,"q":0,"r":0,"s":0,"t":0,"u":0,"v":0,"w":0,"x":0,"y":0,"z":0}

for i in a:
    alp[str(i)]+=1

ans=0
for i in alp:
    if alp[i]%2!=0:
        ans+=1
if ans==0:
    ans+=1

print ans

Submission status: Wrong Answer

Solution code:
a=list(raw_input())
alp={"a":0,"b":0,"c":0,"d":0,"e":0,"f":0,"g":0,"h":0,"i":0,"j":0,"k":0,"l":0,"m":0,"n":0,"o":0,"p":0,"q":0,"r":0,"s":0,"t":0,"u":0,"v":0,"w":0,"x":0,"y":0,"z":0}

for i in a:
    alp[str(i)]+=1

ans=1
for i in alp:
    if alp[i]%2!=0:
        ans+=1
print ans

Submission status: Wrong Answer

Solution code:
def main():
    S = input()

    str_ = dict()
    for s in S:
        str_[s] = str_.get(s, 0) + 1

    even = 0
    odd = 0
    for key, val in str_.items():
        if val % 2:
            odd += 1
        else:
            even += 1

    if odd <= 1:
        print(1)
    elif even == 0:
        print(odd)
    else:
        print(odd)

main()

Submission status: Wrong Answer

Solution code:
s = input()
n = len(s)
cA = ord('a')

su = [0]*n
cp = 1 << (ord(s[0])-cA)
P = {cp: 0}
prev = [-1]*26
dp = [10**18 for i in range(n+1)]

dp[0] = 1
su[0] = cp
prev[ord(s[0])-cA] = 0
for i in range(1, n):
    code = ord(s[i]) - cA
    dp[i] = min(dp[i], dp[i-1] + 1)
    pv = prev[code]
    if pv != -1:
        need = su[i-1] ^ su[pv]
        #print(need, pv)
        state = need ^ su[pv] ^ (1 << code)
        #print(i, state, P)
        if state == 0:
            dp[i] = 1
        elif state in P:
            j = P[state]
            dp[i] = min(dp[i], dp[j] + 1)
    if cp == 0:
        dp[i] = 1
    if cp in P:
        j = P[cp]
        dp[i] = min(dp[i], dp[j] + 1)
    cp ^= 1 << code
    if cp == 0:
        dp[i] = 1
    if cp in P:
        j = P[cp]
        dp[i] = min(dp[i], dp[j] + 1)
    else:
        P[cp] = i
    prev[code] = i
    su[i] = cp

    for j in range(26):
        pv = prev[j]
        if pv != -1:
            need = su[i] ^ su[pv]
            state = need ^ su[pv] ^ (1 << j)
            if state == 0:
                dp[i] = 1
            elif state in P:
                k = P[state]
                dp[i] = min(dp[i], dp[k] + 1)
#print(dp)
print(dp[n-1])