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

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
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()

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: Runtime Error

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
print(dp[cums[-1]])

Submission status: Runtime Error

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

import math

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, math.inf) + 1 for i in range(26)),
            s.get(pat, math.inf))

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

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;
typedef long long int uli;
int f[(1<<26)+10];
const int oo=1e9;
int main(){
  for(int i=0;i<(1<<26);i++)f[i]=oo;
  string s;
  cin>>s;
  int h=0,fi;
  f[0]=0;
  for(char ch:s){
    h^=(1<<(ch-'a'));
    fi=1+f[h];
    for(int i=0;i<26;i++){
      int m=(h^(1<<i));
      fi=min(fi,1+f[m]);
    }
    f[h]=min(f[h],fi);
  }
  printf("%d\n",fi); 
  return 0;
}

Submission status: Runtime Error

Solution code:
s = input()
tmp = set()
ss = []
for x in s:
    if x in tmp:
        tmp.add(x)
    else:
        tmp.remove(x)
    ss.append(tmp)

n = [0]
for i in range(len(s)):
    n.append(0)
    n[i] = n[i-1] + 1
    for j in range(i-1, -1, -1):
        t = set(ss[j]).symmetric_difference(set(ss[i]))
        if len(t) <= 1 and n[j-1] + 1 < n[i]:
            n[i] = n[j-1]+1
print(n[len(s) - 1])

Submission status: Runtime Error

Solution code:
s = raw_input()

def process(d, c):
  d[c] = d.get(c, 0) + 1
  d['odds'] += 1 if d[c] % 2 == 1 else -1

  d['child'] = filter(lambda v:process(v,c), d['child'])
  if d['odds'] <= 1:
    d['child'].append({ 'child': [], 'odds': 0 })

  return d['odds'] > 0

root = {
  'child': [],
  'odds': 0
}

for c in s:
  process(root, c)

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

Submission status: Runtime Error

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: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000000)
s = input()
def check(str,flag):
	print(str)
	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: Runtime Error

Solution code:
import functools

alpha = "abcdefghijklmnopqrstuvwxyz"

resultmap = {}

def replace(s:str):
    l = [(s.index(a) if a in s else -1,a) for a in alpha]
    l = [a for a in l if a[0] != -1]
    t = sorted(l,key=lambda k:k[0])
    # print(t)
    for bef,aft in [(c,alpha[i]) for i,c in t]:
        # print(bef,aft)
        s = s.replace(bef,aft)
    return s


def check(s):
    s = replace(s)
    if s in resultmap:
        return resultmap[s]
    # print(s)
    dict = {w: (False, -1, -1) for w in alpha}
    for i, c in enumerate(s):
        if dict[c][0]:
            dict[c] = (False, dict[c][1], dict[c][2])
        else:
            f = dict[c][1]
            dict[c] = (True, i if f == -1else f, i)

    # print(dict)
    aaaa = [c for c in alpha if dict[c][0]]
    # print(aaaa)

    if len(aaaa) <= 1:
        resultmap[s]=1
        return 1

    ser = sorted([dict[a][2] for a in aaaa])
    target1 = ser[1]
    ser = sorted([dict[a][1] for a in aaaa])
    target2 = ser[-2]
    # print(target1)
    # print(target2)
    r =  min((1 + check(s[target1:])),1+check(s[:target2+1]))
    resultmap[s]=r
    return r


    # return functools.reduce(lambda a, b: a + b, aaaa)


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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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
if val>5:
    raise
print(val)

Submission status: Runtime Error

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
if val>6:
    raise
print(val)

Submission status: Runtime Error

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

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

memo2 = [[-1 if i != j else 1 for i in range(len(S))] for j in range(len(S))]
def partition(start,end):
	if memo2[start][end-1] > 0:
		return memo2[start,end-1]
	elif isPal(start,end):
		memo2[start][end-1] = 1
		return 1
	else:
		ret = 1000000
		for s2 in [s for s in range(start+1, end) if isPal(start,s)]:
			memo2[start][s2-1] = 1
			if memo2[s2][end-1] > 0:
				ret = min(ret, memo2[s2][end-1] + 1)
			else:
				a = partition(s2,end)
				ret = min(ret, a + 1)
			if ret == 2:
				break
		memo2[start][end-1] = ret
		return ret

print(partition(0,len(S)))

Submission status: Runtime Error

Solution code:
import sys
import re
import math
import bisect

#[left, right)の文字列を並び替えて回文が作れるかどうか
def is_pal(left, right):
    n_odd = 0
    n_even = 0
    for c, locs in c_loc.items():
        #各locsについて、left以上right未満である要素の数をカウント
        l_idx = bisect.bisect_left(locs, left)
        r_idx = bisect.bisect_left(locs, right)
        n = r_idx - l_idx
#        print(n)
        if n % 2 == 0:
            n_even += 1
        else:
            n_odd += 1
    return n_odd <= 1

#与えられたインデックスから文字列の最後まで、回文が作れるかどうかチェック
#最少の分割数を返す
def solve(s_idx):
    if s_idx == N-1:
        return 1
    
    if s_idx == N:
        return 0

    res = 9999999
    for e_idx in range(s_idx+1, N+1):
        if is_pal(s_idx, e_idx):
            #print(s_idx, e_idx, S[s_idx:e_idx])
            tmp = solve(e_idx)
            res = min(res, tmp)
    return res + 1

S = input()
N = len(S)
c_loc = {}
for i in range(0, len(S)):
    c = S[i]
    tmp = c_loc.get(c, [])
    tmp.append(i)
    c_loc[c] = tmp

print(solve(0))

Submission status: Runtime Error

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
if val>3:
    raise
print(val)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)
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

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

memo2 = [[-1 if i != j else 1 for i in range(len(S))] for j in range(len(S))]
def partition(start,end):
	if memo2[start][end-1] > 0:
		return memo2[start,end-1]
	elif isPal(start,end):
		memo2[start][end-1] = 1
		return 1
	else:
		ret = 1000000
		for s2 in [s for s in range(start+1, end) if isPal(start,s)]:
			memo2[start][s2-1] = 1
			if memo2[s2][end-1] > 0:
				ret = min(ret, memo2[s2][end-1] + 1)
			else:
				a = partition(s2,end)
				ret = min(ret, a + 1)
			if ret == 2:
				break
		memo2[start][end-1] = ret
		return ret

print(partition(0,len(S)))

Submission status: Runtime Error

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
if val>2:
    raise
print(val)

Submission status: Runtime Error

Solution code:
inf = float("inf")
def kaibun(x):
    species = set(list(x))
    lst = []
    for char in species:
        lst.append(x.count(char) % 2)
    if lst.count(1) <= 1:
        return 1
    else:
        return inf

def rec(curr, rest):
    if (curr, rest) in memo.keys():
        return memo[(curr, rest)]
    if rest == "":
        memo[(curr, rest)] = kaibun(curr)
    else:
        one_or_inf = kaibun(curr + rest[0])
        if one_or_inf == 1:
            drop = kaibun(curr + rest[0]) + rec("", rest[1:])
        else:
            drop = inf
        keep = rec(curr + rest[0], rest[1:])
        memo[(curr, rest)] = min(drop, keep)
    return memo[(curr, rest)]

memo = {}

print(rec("", input()))

Submission status: Runtime Error

Solution code:
inf = float("inf")
def kaibun(x):
    species = set(list(x))
    lst = []
    for char in species:
        lst.append(x.count(char) % 2)
    if lst.count(1) <= 1:
        return 1
    else:
        return inf

def rec(curr, rest):
    if rest == "":
        return kaibun(curr)
    else:
        one_or_inf = kaibun(curr + rest[0])
        if one_or_inf == 1:
            drop = kaibun(curr + rest[0]) + rec("", rest[1:])
        else:
            drop = inf
        keep = rec(curr + rest[0], rest[1:])
        return min(drop, keep)

print(rec("", input()))

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>

#define REP(i,n) for(int i = 0; i < n; i++)
#define RREP(i, a, b) for (int i = a; i < (b); i++)
#define FOR(i, n) for (int i = n; i >= 0; i--)
using namespace std;
typedef long long ll;

int main(){
    string in;
    cin >> in;
    ll n = in.length();
    ll dp[n];
    REP(i,n){
        dp[i] = -1;
    }
    dp[0] = 1;
    ll memo[n][26];
    char REF = 'a';
    ll index[26];
    REP(i,26){
        index[i] = 0;
        REP(j,n){
            memo[j][i] = 0;
        }
    }
    int init = in[0] - REF;
    index[init]++;
    memo[0][init]++;
    RREP(i,1,n){
        char now = in[i];
        int i_now = now - REF;
        index[i_now]++;
        ll mini = 1000000;
        REP(j,i){
                ll odd = 0;
                REP(k,26){
                    if((index[k] - memo[j][k]) % 2 != 0){
                        odd++;
                        if(odd > 1) break;
                    }
                }
                if(odd <= 1 && mini > dp[j] + 1){
                    mini = dp[j] + 1;
                }
        }
        ll odd = 0;
        REP(j,26){
            memo[i][j] = index[j];
            if(index[j] % 2 != 0){
                odd++;
            }
        }
        if(odd < 2) mini = 1;
        dp[i] = mini;
    }
    cout << dp[n-1] << "\n";
    return 0;
}

Submission status: Runtime Error

Solution code:
from string import ascii_lowercase
import heapq

cd = {c: 1 << i for i, c in enumerate(ascii_lowercase)}


def solve(s):
    queue = [(0, s)]
    while queue:
        n, s = heapq.heappop(queue)
        if not s:
            return n
        b = 0
        for i, c in enumerate(s):
            b ^= cd[c]
            if bin(b).count('1') <= 1:
                heapq.heappush(queue, (n + 1, s[i + 1:]))


print(solve(input()))