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:
#! usr/bin/env python3
#D:

def is_kaibun (S):
	#戻り値が0:回文,1:回文無理
	l = len(S)
	S.sort()

	i = 0


	if l % 2 == 1:
		sign = 0
		
		while True:
			if i >= l-1:
				return 0
			elif S[i] == S[i+1]:
				i += 2
			else:
				if sign == 1:
					return 1
				else:
					sign += 1
					i += 1

	else:
		while True:
			if i >= l-1:
				return 0
			elif S[i] == S[i+1]:
				i += 2
			else:
				return 1



	

def is_kaibun3(S):
	if (S[0] == S[1]) or (S[0] == S[2]) or (S[1] == S[2]):
		return 0
	else:
		return 1



S = list(input())
devide = 0


def maxkaibun(S,front,last):
	global devide 
	i = len(S)

	for length in range(i,0,-1):
		for start in range(i-length+1):
			if length  == 1:
				devide += i
				return 0 

			elif length == 2:
				if S[start] == S[start+1]:

					if (front == start) or ((start+length+1) == last):
						return 0

					maxkaibun(S[front:start],front,start)
					maxkaibun(S[start+length+1:last],start+length+1,last)
					return 0

			elif length == 3:
				if (is_kaibun3(S[start:start+length+1]) == 0):
					devide += 1
				
					if (front == start) or ((start+length+1) == last):
						return 0

					maxkaibun(S[front:start],front,start)
					maxkaibun(S[start+length+1:last],start+length+1,last)
					return 0

			if (is_kaibun(S[start:start+length+1]) == 0):
				devide += 1

				if (front == start) or ((start+length+1) == last):
					return 0

				maxkaibun(S[front:start],front,start)
				maxkaibun(S[start+length+1:last],start+length+1,last)
				return 0

maxkaibun(S,0,len(S))
print(devide)

Submission status: Wrong Answer

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

def is_kaibun (S):
	#戻り値が0:回文,1:回文無理
	l = len(S)
	S.sort()

	i = 0


	if l % 2 == 1:
		sign = 0
		
		while True:
			if i >= l-1:
				return 0
			elif S[i] == S[i+1]:
				i += 2
			else:
				if sign == 1:
					return 1
				else:
					sign += 1
					i += 1

	else:
		while True:
			if i >= l-1:
				return 0
			elif S[i] == S[i+1]:
				i += 2
			else:
				return 1


def is_kaibun2(S):
	if S[0] == S[1]:
		return 0
	else:
		return 1

def is_kaibun3(S):
	if (S[0] == S[1]) or (S[0] == S[2]) or (S[1] == S[2]):
		return 0
	else:
		return 1



S = list(input())
devide = 0


def maxkaibun(S,front,last):
	global devide 
	i = len(S)

	for length in range(i,0,-1):
		for start in range(i-length+1):
			if length  == 1:
				devide += i
				return 0 

			elif length == 2:
				if (is_kaibun2(S[start:start+length+1]) == 0):
					devide += 1
				
				if (front == start) or ((start+length+1) == last):
					return 0

				maxkaibun(S[front:start],front,start)
				maxkaibun(S[start+length+1:last],start+length+1,last)
				return 0

			elif length == 3:
				if (is_kaibun3(S[start:start+length+1]) == 0):
					devide += 1
				
				if (front == start) or ((start+length+1) == last):
					return 0

				maxkaibun(S[front:start],front,start)
				maxkaibun(S[start+length+1:last],start+length+1,last)
				return 0

			if (is_kaibun(S[start:start+length+1]) == 0):
				devide += 1

				if (front == start) or ((start+length+1) == last):
					return 0

				maxkaibun(S[front:start],front,start)
				maxkaibun(S[start+length+1:last],start+length+1,last)
				return 0

maxkaibun(S,0,len(S))
print(devide)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10000000)

s = input()

def check(str,flag):
	if str == "":
		return True
	flag += str.count(str[0])%2
	if flag >1:
		return False
	else:
		return check(str.replace(str[0],""),flag)

def check2(str,x):
	if str=="" or check(str,0):
		return x
	count = len(str)-1
	while(not check(str[0:count],0)):
		count -= 1
	return check2(str[count:],x+1)

a = min(check2(s,1),check2(s[::-1],1))
print(a)

Submission status: Wrong Answer

Solution code:
from string import ascii_lowercase

cd = {c: 1 << i for i, c in enumerate(ascii_lowercase)}
bt = set(cd.values())
bt.add(0)


def solve(s):
    q = {s}
    n = 0
    while True:
        nq = set()
        for s in q:
            if not s:
                return n
            b, li = 0, 0
            for i, c in enumerate(s):
                b ^= cd[c]
                if b in bt:
                    li = i
            nq.add(s[li + 1:])
            b, li = 0, 0
            for i, c in enumerate(s[::-1]):
                b ^= cd[c]
                if b in bt:
                    li = i
            nq.add(s[:len(s) - li - 1])

        q = nq
        n += 1


print(solve(input()))

Submission status: Wrong Answer

Solution code:
s=list(input())

N={}

for ss in "abcdefghijklmnopqrstuvwxyz":
    N[ss]=0


count=0

for ss in s:
    N[ss]+=1
    if N[ss]%2==1:
        count+=1
    else:
        count-=1


print(max(1,count))

Submission status: Wrong Answer

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


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

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

Submission status: Wrong Answer

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


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

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 not in P:
        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)
ans = dp[n-1]
#print(dp)
for i in range(26):
    pv = prev[i]
    if pv != -1:
        need = su[n-1] ^ su[pv]
        #print(bin(need), pv)
        state = need ^ su[pv] ^ (1 << i)
        #print(i, state, P)
        if state == 0:
            ans = 1
        elif state in P:
            j = P[state]
            #print(">", i, j)
            ans = min(ans, dp[j] + 1)
print(ans)

Submission status: Wrong Answer

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

def is_kaibun (S):
	#戻り値が0:回文,1:回文無理
	l = len(S)
	S.sort()

	i = 0


	if l % 2 == 1:
		sign = 0
		
		while True:
			if i >= l-1:
				return 0
			elif S[i] == S[i+1]:
				i += 2
			else:
				if sign == 1:
					return 1
				else:
					sign += 1
					i += 1

	else:
		while True:
			if i >= l-1:
				return 0
			elif S[i] == S[i+1]:
				i += 2
			else:
				return 1


S = list(input())
devide = 0


def maxkaibun(S,front,last):
	global devide 
	i = len(S)

	if i == 0:
		return 0


	for length in range(i,0,-1):
		for start in range(i-length+1):
			if length  == 1:
				devide += i
				return 0 

			if (is_kaibun(S[start:start+length+1]) == 0):
				devide += 1
				maxkaibun(S[front:start],front,start)
				maxkaibun(S[start+length+1:last],start+length+1,last)
				return 0

maxkaibun(S,0,len(S))
print(devide)

Submission status: Wrong Answer

Solution code:
from collections import Counter
from string import ascii_lowercase
from functools import lru_cache
import sys
s = input()
sys.setrecursionlimit(100000000)
tmp_c = Counter(s)
val = sum(tmp_c[s_tmp]%2 for s_tmp in ascii_lowercase)
if val==0:
    val=1
print(val)
@lru_cache(maxsize=-1)
def solve(S):
    if len(S)==1:
        return 1
    if len(S)==0:
        return 0
    tmp_c = Counter(S)
    if sum(tmp_c[s_tmp]%2 for s_tmp in ascii_lowercase)<=1:
        return 1

    res = len(S)
    counter = Counter()
    for i,val_s in enumerate(S):
        counter[val_s]+=1
        if sum(counter[s_tmp]%2 for s_tmp in ascii_lowercase)==1:
             res= min(res,1+ solve(S[i+1:][::-1]))
    return res

Submission status: Wrong Answer

Solution code:
s=input()
from collections import Counter
d=Counter(s)
dd=[]
for i,j in d.items():
 if j%2==1:
   dd.append(i)
l=len(dd)
if l==0:
  l=1

print(l)

Submission status: Wrong Answer

Solution code:
from collections import Counter
from string import ascii_lowercase
from functools import lru_cache
import sys
s = input()
sys.setrecursionlimit(100000000)
tmp_c = Counter(s)
val = sum(tmp_c[s_tmp]%2 for s_tmp in ascii_lowercase)
if val==0:
    val==1
print(val)
@lru_cache(maxsize=-1)
def solve(S):
    if len(S)==1:
        return 1
    if len(S)==0:
        return 0
    tmp_c = Counter(S)
    if sum(tmp_c[s_tmp]%2 for s_tmp in ascii_lowercase)<=1:
        return 1

    res = len(S)
    counter = Counter()
    for i,val_s in enumerate(S):
        counter[val_s]+=1
        if sum(counter[s_tmp]%2 for s_tmp in ascii_lowercase)==1:
             res= min(res,1+ solve(S[i+1:][::-1]))
    return res

Submission status: Wrong Answer

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


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

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 not in P:
        P[cp] = i
    prev[code] = i
    su[i] = cp
ans = dp[n-1]
#print(dp)
for i in range(26):
    pv = prev[i]
    if pv != -1:
        need = su[n-1] ^ su[pv]
        #print(bin(need), pv)
        state = need ^ su[pv] ^ (1 << i)
        #print(i, state, P)
        if state == 0:
            ans = 1
        elif state in P:
            j = P[state]
            #print(">", i, j)
            ans = min(ans, dp[j] + 1)
print(ans)

Submission status: Wrong Answer

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


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

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)
    cp ^= 1 << code
    if cp not in P:
        P[cp] = i
    prev[code] = i
    su[i] = cp
ans = dp[n-1]
#print(dp)
for i in range(26):
    pv = prev[i]
    if pv != -1:
        need = su[n-1] ^ su[pv]
        #print(bin(need), pv)
        state = need ^ su[pv] ^ (1 << i)
        #print(i, state, P)
        if state == 0:
            ans = 1
        elif state in P:
            j = P[state]
            #print(">", i, j)
            ans = min(ans, dp[j] + 1)
print(ans)

Submission status: Wrong Answer

Solution code:
s=list(input())

N={}

for ss in s:
    try:
        N[ss]+=1
    except:
        N[ss]=1

count=0

for sN in N:
    if N[sN]%2==1:
        count+=1


print(max(1,count))

Submission status: Wrong Answer

Solution code:
s = input()
ki = 0
for i in range(26):
    w = chr(97+i)
    if s.count(w) % 2 == 1:
        ki += 1
if ki != 0:
    print(ki)
else:
    print(1)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10000000)

s = input()

def check(str):
	temp = {}
	for i in str:
		if i not in temp:
			temp[i] = 0
		temp[i]+=1
	flag = 0
	for i in temp:
		flag += temp[i]%2
		if flag >1:
			return False
	return True

def check2(str,x):
	if str=="" or check(str):
		return x
	count = len(str)-1
	while(not check(str[0:count])):
		count -= 1
	return check2(str[count:],x+1)

a = min(check2(s,1),check2(s[::-1],1))
print(a)

Submission status: Wrong Answer

Solution code:
from collections import Counter

s = input()

def kai_judge(l):
    flag = 0
    for _, cnt in Counter(l).most_common():
        if cnt % 2 == 1:
            flag += 1
        if flag >= 2:
            return False
    else:
        return True 
        
def kaibun(l):
    for i in range(len(l), 0, -1):
        if kai_judge(l[:i]):
            return l[i:]
        
l_ans = 0
s_rest = s
while(len(s_rest) > 1):
    s_rest = kaibun(s_rest)
    l_ans += 1
    if len(s_rest) == 1:
        l_ans += 1
        break
    
r_ans = 0
s_rest = s[::-1]
while(len(s_rest) > 1):
    s_rest = kaibun(s_rest)
    r_ans += 1
    if len(s_rest) == 1:
        r_ans += 1
        break
    
print(min(l_ans, r_ans))

Submission status: Wrong Answer

Solution code:
S = input()
ans = 0
for i in range(26):
	c = chr(ord('a') + i)
	ans += S.count(c) % 2
print(max(ans,1))

Submission status: Wrong Answer

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

def is_kaibun (S):
	#戻り値が0:回文,1:回文無理
	l = len(S)
	S.sort()

	i = 0


	if l % 2 == 1:
		sign = 0
		
		while True:
			if i >= l-1:
				return 0
			elif S[i] == S[i+1]:
				i += 2
			else:
				if sign == 1:
					return 1
				else:
					sign += 1
					i += 1

	else:
		while True:
			if i >= l-1:
				return 0
			elif S[i] == S[i+1]:
				i += 2
			else:
				return 1


S = list(input())
i = len(S)

front = 0
last = i

devide = 0

while True:
	if front == last:
		break

	if (is_kaibun(S[front:i]) == 0 ) or (i == front):
		devide += 1
		front = i
		i = last

	else:
		i -= 1

print(devide)

Submission status: Wrong Answer

Solution code:
inputs = input()

i_dict ={}

inputs = list(inputs)

for i in inputs:
    if i not in i_dict:
        i_dict[i] = 1
    else:
        i_dict[i] += 1

for k, v in i_dict.items():
    i_dict[k] = v % 2
    
ans = 0
for v in i_dict.values():
    ans += v

if ans == 0:
    print(1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
S = input()
A = [[0 for i in range(26)] for j in range(len(S) + 1)]
for i in range(1,len(S)+1):
	c = S[i-1]
	A[i] = [n for n in A[i-1]]
	A[i][ord(c)-ord('a')] += 1

def isPal(start,end):
	l = [(A[end][i] - A[start][i]) % 2 for i in range(26)]
	odd = l.count(1)
	return odd <= 1

ans = 0
'''
s = 0
while s != len(S):
	e = len(S)
	while not isPal(s,e):
		e -= 1
	ans += 1
	s = e
'''
e = len(S)
while e != 0:
	s = 0
	while not isPal(s,e):
		s += 1
	ans += 1
	e = s
print(ans)

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():
    s = [2**(ord(c)-97) for c in S()]
    t = set()
    for c in s:
        if c in t:
            t.remove(c)
        else:
            t.add(c)

    return len(t) or 1


print(main())

Submission status: Wrong Answer

Solution code:
s = input()
a = [0]*26
for i in s:
	a[ord(i)-ord('a')] += 1
k = 0
for i in a:
	if i%2 == 1:
		k+=1
if k==0:
	k = 1
print(k)

Submission status: Wrong Answer

Solution code:
import functools

alpha = "abcdefghijklmnopqrstuvwxyz"
def check(s):
    dict = {w:0 for w in alpha}
    for c in s:
        if dict[c]==1:
            dict[c]=0
            continue
        if dict[c]==0:
            dict[c]=1
    aaaa = [dict[c] for c in alpha]
    return functools.reduce(lambda a,b:a+b,aaaa)

def main():
    n = check(input())
    print(max(1,n))

    # total = functools.reduce(lambda a, b: a * (2 if b % 2 == 1 else 1),A)
    # print(pow(3 ,len(A)-1)*total)
    # # print(123)
    # b = [int(a) for a in input().split(" ")]
    # print(b)
    # [input() for a in range(3)]


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from itertools import accumulate

s = input()
N = len(s)
cnt = [[0] * (N+1) for _ in range(26)]
for i in range(N):
    cnt[ord(s[i]) - ord('a')][i+1] += 1
for c in range(26):
    cnt[c] = list(accumulate(cnt[c]))

dp = [(0, 0)]
for i in range(N):
    tmp = dp[:]
    res = 0
    while tmp:
        cost, j = heappop(tmp)
        odd = 0
        for c in range(26):
            if (cnt[c][i+1] - cnt[c][j]) % 2 == 1:
                odd += 1
        if odd <= 1:
            res = cost + 1
            break
    heappush(dp, (res, i + 1))
for cost, j in dp:
    if j == N:
        print(cost)
        break

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

s = input()
N = len(s)
cnt = [[0] * (N+1) for _ in range(26)]
for i in range(N):
    cnt[ord(s[i]) - ord('a')][i+1] += 1
for c in range(26):
    cnt[c] = list(accumulate(cnt[c]))

dp = [0] * (N+1)

for i in range(N):
    dp[i+1] = dp[i] + 1
    for j in range(i):
        odd = 0
        for c in range(26):
            if (cnt[c][i+1] - cnt[c][j]) % 2 == 1:
                odd += 1
        if odd <= 1:
            dp[i+1] = min(dp[i+1], dp[j] + 1)
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    S = input()
    a = {j: i for i, j in enumerate('abcdefghijklmnopqrstuvwxyz')}
    S = [a[i] for i in S]

    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, dict_parity[parity]+1)
        ans = min(
            [ans]+[dict_parity.get(parity ^ 2**j, ans)+1 for j in range(26)])
        dict_parity[parity] = min(ans, dict_parity.get(parity, ans))
    print(ans)


main()

Submission status: Time Limit Exceeded

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

    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 dict_parity[parity] > ans:
            dict_parity[parity] = i+1
    print(dp[-1])


main()

Submission status: Time Limit Exceeded

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)))
if ls[-1] == 0:
  print(1)
  exit()
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: Time Limit Exceeded

Solution code:
def main():
    import sys
    from collections import defaultdict
    from bisect import bisect_left
    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_list = h2i[h]
            ii = bisect_left(ii_list, i+1)
            if ii < len(ii_list):
                ii = ii_list[ii]
                if i:
                    dp[ii] = min(dp[ii], dp[i])
                else:
                    dp[ii] = 1
        for j in range(26):
            new_h = h ^ (1 << j)
            if h2i[new_h]:
                ii_list = h2i[new_h]
                ii = bisect_left(ii_list, i+1)
                if ii < len(ii_list):
                    ii = ii_list[ii]
                    dp[ii] = min(dp[ii], dp[i] + 1)
    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
S = input()

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

masks = [1<<k for k in range(26)]
cums = [0]
for c in S:
    cums.append(cums[-1] ^ masks[ctoi(c)])
if cums[-1] == 0:
    print(1)
    exit()
maskset = set(masks)

dp = {0:0}
for b in cums:
    for m in maskset:
        msk = b^m
        if msk in dp:
            if b in dp:
                dp[b] = min(dp[b], dp[msk]+1)
            else:
                dp[b] = dp[msk]+1
print(dp[cums[-1]])

Submission status: Time Limit Exceeded

Solution code:
S = input()

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

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

dp = {0:0}
for i,b in enumerate(cums):
    for m in masks:
        msk = b^m
        if msk in dp:
            if b in dp:
                dp[b] = min(dp[b], dp[msk]+1)
            else:
                dp[b] = dp[msk]+1
print(dp[cums[-1]])

Submission status: Time Limit Exceeded

Solution code:
S = input()

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

masks = [1<<k for k in range(26)]
dp = {0:0}
for i,b in enumerate(cums):
    for m in masks:
        msk = b^m
        if msk in dp:
            if b in dp:
                dp[b] = min(dp[b], dp[msk]+1)
            else:
                dp[b] = dp[msk]+1
print(dp[cums[-1]])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
S = input().rstrip()

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 i,b in enumerate(cums):
    for k in range(26):
        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
print(dp[cums[-1]])

Submission status: Time Limit Exceeded

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 i,b in enumerate(cums):
    for k in range(26):
        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
print(dp[cums[-1]])

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
INF = 10**9

alph = "abcdefghijklmnopqrstuvwxyz"
to_int = {v: i for i, v in enumerate(alph)}
dp = [INF]*(n+1)
dp[0] = 0

for i in range(n):
    tmp = 0
    for j in range(i+1)[::-1]:
        tmp ^= 1 << to_int[s[j]]
        if bin(tmp).count("1") <= 1:
            dp[i+1] = min(dp[j] + 1, dp[i+1])
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
s = input()
n = len(s)
bits = dict()
bits[0] = 0
bit = 0
for i in range(n):
	x = ord(s[i])-97
	bit ^= (1<<x)
	for j in range(26):
		new_bit = bit ^ (1<<j)
		if new_bit in bits:
			#print(bin(bit)[2:], bin(new_bit)[2:])
			if bit in bits:
				bits[bit] = min(bits[bit], bits[new_bit] + 1)
			else:
				bits[bit] = bits[new_bit] + 1
			#print(bits[bit])
		#print("-----")
if bit not in bits:
	print(-1)
else:
	print(max(1, bits[bit]))

Submission status: Time Limit Exceeded

Solution code:
import os
import string
import sys
from collections import Counter
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


S = sys.stdin.buffer.readline().decode().rstrip()
N = len(S)

lefts = [{c: 0 for c in string.ascii_lowercase} for _ in range(N)]
rights = [{c: 0 for c in string.ascii_lowercase} for _ in range(N)]
for i in range(1, N):
    for c in string.ascii_lowercase:
        lefts[i][c] = lefts[i - 1][c]
    lefts[i][S[i - 1]] += 1
for i in reversed(range(N - 1)):
    for c in string.ascii_lowercase:
        rights[i][c] = rights[i + 1][c]
    rights[i][S[i + 1]] += 1
total = Counter(S)


def dump(counter):
    for c in sorted(counter.keys()):
        if counter[c] > 0:
            print(c, counter[c])
    print()


@lru_cache(maxsize=None)
def count_palindrome(l, r):
    if r <= l:
        assert False
    if l + 1 == r:
        return 1
    counts = total.copy()
    for c in string.ascii_lowercase:
        counts[c] -= lefts[l][c]
        counts[c] -= rights[r - 1][c]
    odds = 0
    for c in counts.values():
        odds += c % 2
    if odds <= 1:
        return 1

    ret = INF
    for i in range(l + 1, r):
        # i で split するときの両側の数
        cnt = count_palindrome(l, i) + count_palindrome(i, r)
        ret = min(cnt, ret)
    return ret


ans = count_palindrome(0, N)
print(ans)

Submission status: Time Limit Exceeded

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)

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[max(acc2idx[hash_cur])][hash_cur] = min(dp[max(acc2idx[hash_cur])][hash_cur], dp[i][hash_cur] + 1)
    for j in range(26):
        hash_new = hash_cur ^ (2**j)
        dp[max(acc2idx[hash_new])][hash_new] = min(dp[max(acc2idx[hash_new])][hash_new], dp[i][hash_cur] + 1)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

S = np.array(list(read().rstrip()),np.int32)

Scum = np.bitwise_xor.accumulate(1<<(S-97)).tolist()

bit = 1<<np.arange(26)

INF = 10**9
dp = np.full(1<<26,INF,np.int32)
dp[0] = 0

for cum in Scum:
    x = dp[cum^bit].min() + 1
    if dp[cum] > x:
        dp[cum] = x

answer = max(1,dp[cum])
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

S = read().rstrip()

from collections import defaultdict

INF = 10**9
dp = defaultdict(lambda:INF)
dp[0] = 0

cum = 0
for x in S:
    cum ^= 1<<(x-97)
    x = min(dp[cum^(1<<i)] for i in range(26)) + 1
    if dp[cum] > x:
        dp[cum] = x

answer = max(1,dp[cum])
print(answer)

Submission status: Time Limit Exceeded

Solution code:
S = input()
N = len(S)
INF = float('inf')
dp = [INF] * N
dp[0] = 0
dp2 = {}
dp2[0] = 0
bits = [1 << i for i in range(26)]
x = 0

for i in range(N):
    x = x ^ bits[ord(S[i]) - ord('a')]
    tmp = INF
    if x not in dp2:
        dp2[x] = INF
    tmp = min(tmp, dp2[x])

    for b in bits:
        k = x ^ b
        if k not in dp2:
            dp2[k] = INF
        tmp = min(tmp, dp2[k])

    dp2[x] = min(dp2[x], tmp + 1)
    dp[i] = tmp + 1

print(dp[N - 1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import string

ALPHABETS = string.ascii_lowercase

s = input()
N = len(s)
MAX = 2 * 10 ** 5
a = 0
dp = {}
dp[0] = 0
bits = [2 ** i for i in range(26)]

for c in s:
    a = a ^ bits[ALPHABETS.index(c)]
    dp[a] = min(dp.get(a, MAX), min([dp.get(a ^ 2 ** j, MAX) if not j == -1 else dp.get(a ^ 0, MAX) for j in range(-1, 26)]) + 1)

print(dp[a] if dp[a] != 0 else 1)

Submission status: Time Limit Exceeded

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]] if dp[a[N]] != 0 else 1)

Submission status: Time Limit Exceeded

Solution code:
#  --*-coding:utf-8-*--

def f(str):
    s = {}
    s[0] = 0
    pat = 0

    for c in str:
        pat ^= 2**(ord(c)-97)
        s[pat] = min(
            min(s.get(pat^2**i, len(str)) + 1 for i in range(26)),
            s.get(pat, len(str)))

    if pat == 0:
        return 1

    return s[pat]
            

def test():
    assert f('aabxyyzz') == 2
    assert f('byebye') == 1
    assert f('abcdefghijklmnopqrstuvwxyz') == 26
    assert f('abcabcxabcx') == 3


def main():
    str = input()
    print(f(str))


if __name__ == '__main__':
    main()