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: Time Limit Exceeded

Solution code:
import string

ALPHABETS = string.ascii_lowercase


def is_avairable(a):
    return bin(a).count('1') <= 1

s = input()
N = len(s)
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 = [2 * (10 ** 5) + 1] * (2 ** 26)
dp[0] = 0
for i in range(1, N + 1):
    ns = [dp[a[i] ^ 2 ** j] if not j == -1 else dp[a[i] ^ 0] for j in range(-1, 26)]
    mn = min(ns)
    opt[i] = mn + 1
    if dp[a[i]] > opt[i]:
        dp[a[i]] = opt[i]

print(opt[N])

Submission status: Time Limit Exceeded

Solution code:
import string

ALPHABETS = string.ascii_lowercase


def is_avairable(a):
    return bin(a).count('1') <= 1

s = input()
N = len(s)
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 = [2 * (10 ** 5) + 1] * (2 ** 26)
dp[0] = 0
for i in range(1, N + 1):
    min = 2 * (10 ** 5) + 1
    for j in range(-1, 26):
        n = dp[a[i] ^ 2 ** j] if not j == -1 else dp[a[i] ^ 0]
        if n < min:
            min = n
    opt[i] = min + 1
    if dp[a[i]] > opt[i]:
        dp[a[i]] = opt[i]

print(opt[N])

Submission status: Time Limit Exceeded

Solution code:
import string

ALPHABETS = string.ascii_lowercase


def is_avairable(a):
    return bin(a).count('1') <= 1


s = input()
N = len(s)
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)
for i in range(1, N + 1):
    min = -1
    for j in range(i):
        if is_avairable(a[j] ^ a[i]):
            if opt[j] < min or min < 0:
                min = opt[j]
    opt[i] = min + 1
print(opt[N])

Submission status: Time Limit Exceeded

Solution code:
import copy

s = input()
tmp = set()
ss = []
ss.append(copy.deepcopy(tmp))
for x in s:
    if x in tmp:
        tmp.remove(x)
    else:
        tmp.add(x)
    ss.append(copy.deepcopy(tmp))
n = [0]
#print(list(ss))
for i in range(len(s)):
    n.append(0)
    n[i] = n[i-1] + 1
    for j in range(i, -1, -1):
        if n[j-1] + 1 < n[i]:
            t = set(ss[j]).symmetric_difference(set(ss[i+1]))
            if len(t) <= 1:
                n[i] = n[j-1]+1
#            print(list(t))
#            print(n)
#            print()
print(n[len(s) - 1])

Submission status: Time Limit Exceeded

Solution code:
class init_dic(object):
    """docstring for init_dic."""
    def __init__(self):
        self.__al = []
    def add(self, x):
        if x in self.__al:
            self.__al.remove(x)
        else:
            self.__al.append(x)

    def kaibun(self):
        return len(self.__al) <= 1

    def out(self):
        print(self.__al)

s = input()
n = [0]
for i in range(len(s)):
    n.append(0)
    n[i] = n[i-1] + 1
    t = init_dic()
    t.add(s[i])
    for j in range(i-1, -1, -1):
        t.add(s[j])
        if n[j-1] + 1 < n[i] and t.kaibun():
            n[i] = n[j-1]+1
print(n[len(s) - 1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
s = input()
t = 0
d = {t:0}
for i in (ord(x)-ord('a') for x in s) :
	t ^= 1 << i
	c = d[t] if t in d else 1000000
	for j in range(26) :
		if t^(1<<j) in d :
			c = min(c,d[t^(1<<j)]+1)
	d[t] = c
print(d[t] if d[t] else 1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
s = input()
t = 0
d = [1000000] * (1<<26)
d[0] = 0
for i in s :
	t ^= 1 << (ord(i)-ord('a'))
	for j in range(26) :
		d[t] = min(d[t],d[t^(1<<j)]+1)
print(d[t] if d[t] else 1)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
s = input()
t = 0
d = {t:0}
for i in s :
	t ^= 1 << (ord(i)-ord('a'))
	for j in range(26) :
		d[t] = min(d.get(t,1000000),d.get(t^(1<<j),1000000)+1)
print(d[t] if d[t] else 1)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
s = input()
t = 0
d = {t:0}
for i in s :
	t ^= 1 << (ord(i)-ord('a'))
	for j in range(26) :
		if (t^(1<<j)) in d :
			d[t] = min(d[t] if t in d else int(1e9),d[t^(1<<j)]+1)
print(d[t] if d[t] else 1)

Submission status: Time Limit Exceeded

Solution code:
s = input()

def kaibun3(alp):
    flag1 = False

    for i in range(26):
        if flag1:
            if alp[i] % 2 == 1:
                return False
        else:
            if alp[i] % 2 == 1:
                flag1 = True

    return True

l = len(s)

a = [[0 for i in range(26)] for i in range(l+1)]

for i in range(1, l+1):
    for j in range(26):
        a[i][j] = a[i-1][j]

    ch = ord(s[i-1])-97
    a[i][ch] = a[i][ch] + 1

def test2(left, right):
    cnt = 0

    original_right = right

    while left < right:
        tmp = [a[right][i] - a[left][i] for i in range(26)]
        k = kaibun3(tmp)

        if k:
            cnt += 1
            left = right
            right = original_right + 1

        right -= 1

    return cnt

minimum = 2 * (10**5) + 1

for i in range(l):
    tmp = i + test2(i,l)
    if minimum > tmp:
        minimum = tmp

print(minimum)

Submission status: Time Limit Exceeded

Solution code:
S = input()
dic = {s : S.count(s) for s in set(S)}
memo = [[0 for i in range(len(S)-j)] for j in range(len(S))]
word = [[set() for i in range(len(S)-j)] for j in range(len(S))]

for i in range(len(S)):
    for j in range(len(S)-i):
        if i == 0:
            memo[j][i] = 1
            word[j][i].add(S[i])
        else:
            w = word[j][i-1] ^ {S[i + j]}
            word[j][i] = w
            if len(w) < 2:
                memo[j][i] = 1
            else:
                memo[j][i] = min(memo[j][k] + memo[j+k+1][i-k-1] for k in range(i))

print(memo[0][len(S)-1])

Submission status: Time Limit Exceeded

Solution code:
s = tuple(map(lambda c: ord(c)-ord('a'),input()))

from collections import defaultdict

dp = defaultdict(lambda: len(s))
dp[0] = 0


def it(x):
  for i in range(26):
    yield x ^ (1 << i)

v = 0
for c in s:
  v ^= 1 << c
  dp[v] = min(dp[v],min(dp[i] for i in it(v))+1)

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

Submission status: Time Limit Exceeded

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 = 0
            for i, c in enumerate(s):
                b ^= cd[c]
                if b in bt:
                    nq.add(s[i + 1:])
        q = nq
        n += 1


print(solve(input()))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from string import ascii_lowercase
from functools import lru_cache
import sys
s = input()
sys.setrecursionlimit(100000000)

@lru_cache(maxsize=-1)
def solve(S):
    if len(S)==1:
        return 1
    if len(S)==0:
        return 0
    tmp_c = Counter(S)
    sum_val =sum(tmp_c[s_tmp]%2 for s_tmp in ascii_lowercase)
    if sum_val<=1:
        return 1
    if sum_val==2:
        return 2
    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


print(solve(s))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def can_be_palindrome(s) :
    alpha = defaultdict(lambda: 0)
    for c in s :
        alpha[c] += 1

    flag = False
    for key in alpha.keys() :
        if alpha[key]%2 == 1 :
            if flag :
                return False
            flag = True
    else :
        return True

def main() :
    s = input()
    n = len(s)
    former = 0
    dp1 = [0]*n
    dp1[0] = 1
    for i in range(1, n) :
        if can_be_palindrome(s[0:i+1]) :
            former = i
            dp1[i] = 1
        elif can_be_palindrome(s[former+1:i+1]) :
            dp1[i] = 2
        else :
            dp1[i] = dp1[i-1]+1

    s = s[::-1]
    former = 0
    dp2 = [0]*n
    dp2[0] = 1
    for i in range(1, n) :
        if can_be_palindrome(s[0:i+1]) :
            dp2[i] = 1
        elif can_be_palindrome(s[former+1:i+1]) :
            dp2[i] = 2
        else :
            dp2[i] = dp2[i-1]+1
    print(min(dp1[n-1], dp2[n-1]))

main()

Submission status: Time Limit Exceeded

Solution code:
S = input()
dic = {s : S.count(s) for s in set(S)}
log = {}

def f(S):
    try:
        return log[S]
    
    except KeyError:
        if check(S):
            return 1
        else:
            res = len(S)
            for i in range(1, len(S) - 1):
                res = min(f(S[:i]) + f(S[i:]), res)
                log[S] = res
            return res
    
def check(S):
    flag = False
    for s in set(S):
        if S.count(s) % 2 == 1:
            if flag:
                return False
            else:
                flag = True
    return True

print(f(S))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from string import ascii_lowercase
from functools import lru_cache
import sys
s = input()
sys.setrecursionlimit(100000000)

@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


print(solve(s))

Submission status: Time Limit Exceeded

Solution code:
def main():
  s = input()
  n = len(s)
  cnt = [0] * 26
  sum = [0] * (n + 1)

  for i in range(1, n + 1):
    ind = ord(s[i - 1]) - ord('a')
    cnt[ind] += 1
    sum[i] = sum[i - 1]
    if (cnt[ind] & 1) == 1:
      sum[i] += 1
    else:
      sum[i] -= 1

  f = [0] * (n + 1)
  for i in range(1, n + 1):
    f[i] = 0x7fffffff
    for j in range(i):
      if sum[i] >= sum[j] and sum[i] - sum[j] <= 1:
        f[i] = min(f[i], f[j] + 1)
  print(f[n])


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from string import ascii_lowercase
from functools import lru_cache
import sys
s = input()
sys.setrecursionlimit(100000000)

@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


print(solve(s))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from string import ascii_lowercase
from functools import lru_cache
import sys
s = input()
sys.setrecursionlimit(100000000)

@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
    #print(S)
    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:]))

    return res


print(solve(s))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from string import ascii_lowercase
from functools import lru_cache
import sys
s = input()
sys.setrecursionlimit(100000000)

@lru_cache(maxsize=-1)
def solve(S):
    if len(S)==1:
        return 1
    if len(S)==0:
        return 0
    #print(S)
    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:]))

    return res


print(solve(s))

Submission status: Time Limit Exceeded

Solution code:
S = raw_input()
S = map(ord, S)
a = ord('a')

dp = {}
def get_dp(i):
    if i in dp:
        return dp[i]
    if i == len(S):
        return 0
    num = [0 for t in range(26)]
    dp[i] = len(S) - i

    def check():
        cnt = 0
        for n in num:
            cnt += n % 2 == 1
        return cnt <= 1
    
    for j in range(i, len(S)):
        num[S[j] - a] += 1
        if check():
            dp[i] = min(dp[i], 1 + get_dp(j+1))
    return dp[i]
    

print get_dp(0)

Submission status: Memory Limit Exceeded

Solution code:
s = input()

n = len(s)
inf = 10**6
dp = [inf] * (2**26)
dp[0] = 0

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

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

Submission status: Memory Limit Exceeded

Solution code:
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 = [n]*(1<<26)
  g[0] = 0
  for x in s:
    c ^= 1 << x
    y = g[c] + 1
    for i in range(26):
      y = min(y, g[c ^ (1 << i)] + 1)
    g[c] = min(g[c], y)
  print(y)
  return

solve()

Submission status: Memory 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 = [10**6]*(2**26)
    dict_parity[0] = 0

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


main()

Submission status: Memory Limit Exceeded

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

S = read().rstrip()

INF = 10**9
dp = [INF] * (1<<26)
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: Memory Limit Exceeded

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

S = read().rstrip()

INF = 10**9
dp = [INF] * (1<<26)
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: Memory Limit Exceeded

Solution code:
INF=10**9+7
s=input()
n=len(s)
least=[INF for i in range(1<<26)]
least[0]=0
dp=[INF for i in range(n)]
used=0
for i in range(n):
    a=ord(s[i])-ord('a')
    used^=(1<<a)
    dp[i]=least[used]+1;
    for j in range(26):
        to=used^(1<<j)
        dp[i]=min(dp[i],least[to]+1)
    least[used]=min(least[used],dp[i])
print(dp[n-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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


main()

Submission status: Accepted

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


main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

"""
奇数文字存在する文字がキモ
最低でも答えは奇数文字存在する文字の種類数以上
各ブロックに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

    #print (format(now,"b").zfill(26))

    #dic[now]がokなのは all0かある桁&nalpの桁が1

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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
# MOD = 998244353


# 解説
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[h]: それまでのハッシュが h である位置以前の分割方法の最小値
dp = defaultdict(lambda: INF)
dp[0] = 0
dp[cs[0]] = 1
for i in range(1, N):
    # print(S[i - 1])
    # dumpdp(dp)

    h = cs[i]
    if h == 0:
        continue
    d = 1
    while d < (1 << 26):
        # i から h^d の位置までまとめて 1 つ切り出せる
        dp[h] = min(dp[h], dp[h ^ d] + 1)
        d <<= 1

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

Submission status: Accepted

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: Accepted

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 = {}
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/python3

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

Submission status: Accepted

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 = {}
    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())

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
    # 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])