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 .

Solution (Python):
from collections import defaultdict

s = input()

n = len(s)
inf = 10**6
d = defaultdict(lambda : inf)
d[0] = 0

a = ord('a')
now = 0
for i in range(n):
    si = ord(s[i]) - a
    now = now^(1<<si)
    for j in range(26):
        d[now] = min(d[now], 1+d[now^(1<<j)])

print(max(1,d[now]))

Solution (Python):
INF = 10 ** 9
s = input()
n = len(s)
l = [0] * (n + 1)
for i in range(n):
    l[i + 1] = l[i] ^ (1 << (ord(s[i]) - ord('a')))
dp = dict()
dp[0] = 0
for x in l[1:]:
    if x not in dp:
        dp[x] = INF
    for j in range(26):
        t = x ^ (1 << j)
        if t in dp:
            dp[x] = min(dp[x], dp[t] + 1)
ans = dp[l[-1]]
if ans == 0:
    print(1)
else:
    print(ans)

Solution (Python):
alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
alpha={moji:alphabetlist.index(moji) for moji in alphabetlist}

s=input()
N=len(s)
data=[0]
for i in range(N):
    data.append(2**alpha[s[i]])

for i in range(1,N+1):
    data[i]^=data[i-1]

que={val:2*N for val in data}

dp=[2*N]*(N+1)
dp[0]=0
que[0]=0
S=set([2**i for i in range(26)])
S.add(0)
for i in range(1,N+1):
    for j in S:
        k=data[i]^j
        if k in que:
            dp[i]=min(dp[i],que[k]+1)
    que[data[i]]=min(que[data[i]],dp[i])

print(dp[-1])

Solution (Python):
import sys

readline = sys.stdin.buffer.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

def solve():
  s = [x - 97 for x in ns()]
  n = len(s)
  c = 0
  g = {0:0}
  for x in s:
    c ^= 1 << x
    y = g.get(c, n) + 1
    for i in range(26):
      y = min(y, g.get(c ^ (1 << i), n) + 1)
    g[c] = min(g.get(c, n), y)
  print(y)
  return

solve()

Solution (Python):
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]]
    
    if x >= N + 1: continue
    dp[i + 1] = min(dp[i + 1], x + 1)
  x = d[cs[i + 1]]
  if x <= N: dp[i + 1] = min(dp[i + 1], x + 1)
  d[cs[i + 1]] = min(x, dp[i + 1])
print(dp[-1])

Solution (Python):
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:
        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
    if bit in dic and ind != len(S)-1:
        dic[bit] = min(dic[bit], score)
    else:
        dic[bit] = score

print(dic[bit])

Solution (Python):
def main():
    S = input()
    a = {j: i for i, j in enumerate('abcdefghijklmnopqrstuvwxyz')}
    pow2 = [2**i for i in range(26)]
    S = [pow2[a[i]] for i in S]

    parity = 0
    dict_parity = {0: 0}

    for i, s in enumerate(S):
        parity ^= s
        if parity in dict_parity:
            ans = min(i+1, dict_parity[parity]+1)
        else:
            ans = i+1
        ans = min(
            [ans]+[dict_parity.get(parity ^ j, ans)+1 for j in pow2])
        dict_parity[parity] = min(ans, dict_parity.get(parity, ans))
    print(ans)


main()

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


main()

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


main()

Solution (Python):
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)

Solution (Python):
def main():
    import sys
    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 = {}
    for i in range(N):
        H[i+1] = H[i] ^ (1 << A[i])
        if H[i+1] in h2i:
            h2i[H[i+1]].append(i+1)
        else:
            h2i[H[i+1]] = [i+1]

    dp = [N+1] * (N+1)
    dp[0] = 0
    pow2 = [2**i for i in range(26)]
    for i in range(N):
        h = H[i]
        if h in h2i:
            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 pow2:
            new_h = h ^ j
            if new_h in h2i:
                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()

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

def solve(s):
    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 b in 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
    return dp[cums[-1]]

print(solve(input()))

Solution (Python):

"""
奇数文字存在する文字がキモ
最低でも答えは奇数文字存在する文字の種類数以上
各ブロックに1つだけ奇数文字の文字を奇数個入れるのが良い

左に１つだけ奇数文字がある & 右に少なくとも一つの奇数文字が残っている
→切断すべき

数だけわかればいい
→分割が必要になる条件を考えればよい？

acababcb
a|ab|ab|b ←分割可能ポイント

2文字の間でどこなら分割を置いていいかは求められる
各範囲に最低1つ置いて

26C2かぁ…ちょっとでかくね→3s?

a|bbb|ccc|a

abc
000

a
100
b
110
b
100

abb  -  a   = bb
100 xor 100 = 000

0 xor 0 = 0
1 xor 0 = 1
1 xor 1 = 0

abcdefghijklmnopqrstuvwxyz
10010000000000000000000000
"""

s = input()

alp = "abcdefghijklmnopqrstuvwxyz"
alpdic = {}

for i in range(26):
    alpdic[alp[i]] = i

dic = {}
now = 0
dic[now] = 0

for i in range(len(s)):

    nalp = alpdic[s[i]]
    now ^= 2 ** nalp

    

    

    ans = float("inf")
    if now in dic:
        ans = dic[now]

    for i in range(26):

        nserch = (2 ** i) ^ now
        if nserch in dic:
            ans = min(ans , dic[nserch])

    if now in dic:
        dic[now] = min(dic[now] , ans + 1)

    else:
        dic[now] = ans + 1

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

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

alph = "abcdefghijklmnopqrstuvwxyz"
to_int = {v: i for i, v in enumerate(alph)}
dp = {}
all_state = 0

for i in range(n):
    all_state ^= 1 << to_int[s[i]]
    if all_state not in dp:
        dp[all_state] = i + 1
    for j in range(26):
        bit = all_state ^ (1 << j)
        if bit in dp:
            dp[all_state] = min(dp[bit] + 1, dp[all_state])
    if bin(all_state).count("1") <= 1:
        dp[all_state] = 1
print(dp[all_state])

Solution (Python):
import sys
readline = sys.stdin.readline
from collections import defaultdict

S = list(map(lambda x: ord(x)-97, readline().strip()))
N = len(S)

table = [0] + [1<<S[i] for i in range(N)]
for i in range(1, N+1):
    table[i] ^= table[i-1]

inf = 10**9+7
dp = defaultdict(lambda: inf)
dp[0] = 0

for i in range(1, N+1):
    t = table[i]
    res = 1+dp[t]
    for j in range(26):
        res = min(res, 1+dp[t^(1<<j)])
    dp[t] = min(dp[t], res)
print(res)

Solution (Python):
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:
			
			if bit in bits:
				bits[bit] = min(bits[bit], bits[new_bit] + 1)
			else:
				bits[bit] = bits[new_bit] + 1
			
		
if bit not in bits:
	print(-1)
else:
	print(max(1, bits[bit]))

Solution (Python):
import os
import sys
from collections import defaultdict

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

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




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

cs = [0] * N
h = 0
for i, c in enumerate(S):
    h ^= 1 << (ord(c) - ord('a'))
    cs[i] = h


def dump(h):
    import numpy as np
    print(np.binary_repr(h, 26))


def dumpdp(dp):
    for k in dp.keys():
        if dp[k] < INF:
            dump(k)
            print(dp[k])
    print()



dp = defaultdict(lambda: INF)
dp[0] = 0
dp[cs[0]] = 1
for i in range(1, N):
    
    

    h = cs[i]
    if h == 0:
        continue
    d = 1
    while d < (1 << 26):
        
        dp[h] = min(dp[h], dp[h ^ d] + 1)
        d <<= 1

if cs[-1] == 0:
    print(1)
else:
    print(dp[cs[-1]])

Solution (Python):
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)

Solution (Python):
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])

Solution (Python):
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 = {}
dp[0] = 0
bits = [2 ** i for i in range(26)]
for i in range(n):
  tmp = float("inf")
  for j in bits:
    try:
      tmp = min(dp[h[i+1]^j] + 1,tmp)
    except:
      pass
  try:
    e = dp[h[i+1]]
  except:
    e = float("inf")
  dp[h[i+1]] = min(tmp,e)
print(dp[h[n]] if dp[h[n]] != 0 else 1)

Solution (Python):
s = input()
N = len(s)
a = 0
dp = {}
dp[0] = 0
bits = [2 ** i for i in range(26)]

for c in s:
    a = a ^ bits[ord(c)-ord('a')]
    dp[a] = min(dp.get(a, N), min([dp.get(a ^ bit, N) for bit in bits]) + 1)

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

Solution (Python):


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

    bits = [2**i for i in range(26)]
    lenOfStr = len(str)

    for c in str:
        pat ^= bits[ord(c)-97]
        s[pat] = min(
            min(s.get(pat^bit, lenOfStr) + 1 for bit in bits),
            s.get(pat, lenOfStr))

    if pat == 0:
        return 1

    return s[pat]
            
str = input()
print(f(str))

Solution (Python):


import sys
import itertools

s = next(sys.stdin).rstrip()
n = len(s)
a = 0
succ = [[] for i in range(n)]
d = {0: 0}

def getStep(a):
    ret = None
    for alt in itertools.chain([1 << rot for rot in range(26)], [0]):
        x = a ^ alt
        if x in d and (ret is None or d[x] + 1 < ret):
            ret = d[x] + 1
    return ret

for i, c in enumerate(s):
    ac = ord(c) - 0x61
    br = 1 << ac
    a = a ^ br
    s = getStep(a)
    if s is None: raise ValueError
    if a not in d or s < d[a]: d[a] = s
print(getStep(a))

Solution (Python):
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 = {}
    d2[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 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] if d2[c] else 1



print(main())

Solution (Python):

s = input()
t = 0
d = {t:0}
for i in (ord(x)-ord('a') for x in s) :
	t ^= 1 << i
	d[t] = min(d[t] if t in d else 1000000, min((d[t^(1<<j)] for j in range(26) if t^(1<<j) in d))+1)
print(d[t] if d[t] else 1)

Solution (Python):
import itertools
L=9**9
dp={0:0}
for v in itertools.accumulate(map(lambda c:1<<ord(c)-ord('a'),input()),lambda a,b:a^b):
	dp[v]=min(dp.get(v,L),min(dp.get(v^1<<i, L)for i in range(26))+1)
print(dp[v]+(v==0))

Solution (Python):
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):
    a, b = [], 0
    for c in s:
        b ^= cd[c]
        a.append(b)
    if a[-1] == 0:
        return 1

    dp = {0: 0}
    for b1 in a:
        for b2 in bt:
            b3 = b1 ^ b2
            if b3 not in dp:
                continue
            if b1 in dp:
                dp[b1] = min(dp[b1], dp[b3] + 1)
            else:
                dp[b1] = dp[b3] + 1
    return dp[a[-1]]


print(solve(input()))

Solution (Python):
s = input()
n = len(s)
cA = ord('a')
P = {0: 0}
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
    
    if cur in P:
        dp[i] = min(dp[i], P[cur] + 1)
    
    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])

Solution (Python):
from itertools import accumulate
from operator import xor

s = tuple(map(lambda c: 1 << (ord(c)-ord('a')),input()))
L = len(s)
dp = dict()
dp[0] = 0

for v in accumulate(s, xor):
  dp[v] = min(dp.get(v,L), min(dp.get(v ^ (1 << i), L) for i in range(26))+1)

print(dp[v] + (v == 0))