xsquare-and-palindromes-insertion

Xsquare likes strings a lot but much more, he likes palindromic strings. Today, he has a string S consisting of lower case English letters. Xsquare wants to convert his string S to a palindromic string. For the above purpose to be served , he can insert as many characters  ( possibly zero ) as he wants in his string S such that characters in the new string S can be shuffled to make it a palindrome.

Xsquare is in hurry. Therefore, he wants to accomplish this task with the minimum possible number of insertions in his original string S.

 Input :
First line of input contains a single integer T denoting the number of test cases. First and the only line of each test case contains a string S denoting the original string of the Xsquare.

 Output : 
For each test case, print the required answer.

 Constraints : 

 1 ≤ T ≤ 100 
 1 ≤ |S| ≤ 1000 
 S consists of lower case english alphabets 

 SAMPLE INPUT
5
radar
abc
ab
caa
ccdbb

SAMPLE OUTPUT
0
2
1
0
0

Explanation

TestCase 1 : "radar" is already a palindromic string. Therefore, no insertion is needed.
TestCase 2 : "abc" can be converted to "cbabc" , "bcacb" , "abcba" etc by inserting only 2 characters. 
TestCase 3 : "ab" can be converted to "aba" , "bab" by inserting only 1 character.
TestCase 4 : "caa" can be converted to "aca" only be shuffling letters of string "caa". Therefore, no insertion is needed.
TestCase 5 : "ccdbb" can be converted to "cbdbc" only by shuffling letters. Therefore, no insertion is needed.

Source: hackerearth | Difficulty: EASY
Tags: String algorithms

Fundamentals

Ad-hoc


Solutions:
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def palindrome():
	testcases=eval(input())
	for cases in range(testcases):
		string_input=input()
		dict_hash=dict()
		length_string=len(string_input)
		length_stringinputset=len(set(string_input))
		if(length_string==2 and length_stringinputset==1):
			print(0)
		elif(length_string==3 and length_stringinputset==2):
			print(0)
		elif(length_string==2 and length_stringinputset==2):
			print(1)
		else:
			for ch in list(string_input):
				if(ch in dict_hash):
					dict_hash[ch]+=1
				else:
					dict_hash[ch]=1
			counter=0
			for key in list(dict_hash.keys()):
				if(dict_hash[key]%2==1):
					counter+=1
			if(counter==0):
				print(0)
			elif(counter>0):
				print(counter-1)
			
				
if __name__=='__main__':
	palindrome()


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'
from collections import Counter
t=eval(input())
while t>0:
	t-=1
	s=input()
	s=list(s)
	c=Counter(s)
	l=[]
	f=0
	for key in c:
		l.append(c[key])
	for i in l:
		if i%2!=0:
			f+=1
	if f>1:
		print(f-1)
	else:
		print("0")
			
		
		
	


T = int(input())
for _ in range(T):
	s = input()
	l = [0]*26
	for __ in s:
		v = ord(__)%97
		l[v]+=1
	c = 0
	for __ in l:
		if __%2 != 0:
			c+=1
	if c<=1:
		c=0
	else:
		c-=1
	print(c)
		


for _ in range(eval(input())):
	pal=input()
	count=0
	for j in set(pal):
		n=pal.count(j)
		count+=n&1
	if count>1:	print(count-1)	
	else:print(0)


t = eval(input())
for i in range(t):
	s = input()
	l = len(s)
	set_alph = set()
	for x in s:
		if (x in set_alph):
			set_alph.remove(x)
		else:
			set_alph.add(x)
	if (len(set_alph)==0):
		print(0)
		continue
	print(len(set_alph)-1)	


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def answer(mystr):
	arr = [0 for x in range(1,27)]
	for c in mystr:
		arr[ord(c)-ord('a')] += 1
	numodd = 0
	for i in arr:
		if i%2==1:
			numodd +=1
	
	if numodd<=1:
		return 0

	return numodd-1

n = int(input())
for _ in range(0,n):
	str1 = input()
	print(answer(str1))	


for _ in range(eval(input())):
	s=list(input())
	arr=[0]*26
	for item in s:
		arr[ord(item)-97]+=1
		
	#print arr
	c=0
	for item in arr:
		if item%2!=0:
			c+=1
			
	print(max(c-1,0))


from collections import Counter
t = eval(input())
for _ in range(t):
	counts = Counter(input().strip())
	flag = False
	answer = 0
	for key in list(counts.keys()):
		if not flag and counts[key] % 2:
			flag = True
		elif flag and counts[key] % 2:
			answer += 1
	print(answer)


for _ in range(eval(input())):
	pal=input()
	count=0
	for j in set(pal):
		n=pal.count(j)
		count+=n&1
	if count>1:	print(count-1)	
	else:print(0)


T=int(input())

for i in range(T):
	d=dict()
	n=0
    
	S=input()
	one='';
	for x in S:
		if x in d:
			d[x]=d[x]+1
		else:
			d[x]=1
	for i in list(d.keys()):
		if(d[i]%2!=0):
			one=i
			break;
		
	'''if(one=='' or len(d.keys())==1):
		n=0
	else:	'''
	for i in list(d.keys()):
		if(d[i]%2!=0 and i!=one):
			n+=1
			d[i]=d[i]+1
		
	
	print(n)
		
			
		
		
		


def isPalindrome(str, str_len, set_len):
	set1 = set(str)
	D = {}
	if set_len == 2 and set_len == str_len:
		return 1
	for each in set1:
		D[each] = str.count(each)
	bOdd = 0
# 	print D
	for key in D:
		if D[key] %2 != 0:
			bOdd = bOdd + 1
# 	print bOdd
	if bOdd >= 2:
		return bOdd-1
	return 0
	
def minimal_palindrome(str):
	set1 = set(str)
	length = len(str)
	set_len = len(set1)
	return isPalindrome(str, length, set_len)
	
cases = int(input())
answers = []
for case in range(cases):
	answers.append(minimal_palindrome(input()))
	
for ans in answers:
	print(ans)
	
	


t = int(input())
for i in range(t):
	str = input()
	abc = {}
	inc = 0
	
	for j in str:
		try:
			abc[j]+= 1
		except:
			abc[j] = 1
	for k in abc:
		
		if abc[k] % 2 != 0:
			inc +=1
	if (inc == 0 or inc == 1):
		print(0)
	else :
		op = inc -1
		print(op)


t = int(input())
for i in range(t):
	string = input()
	chars = [0]*26
	for char in string:
		chars[ord(char) - 97] += 1
	even = 0
	odd = 0
	for count in chars:
		if count != 0:
			if count%2 == 0:
				even += 1
			else:
				odd += 1
	if odd==0:
		print(0)
	else:
		print(odd-1)


from collections import Counter
n=eval(input())

for i in range(0,n):
	sent=list(input())
	count=Counter(sent)
	temp=list(count.values())
	dic={"even":0,"odd":0}
	for val in temp:
		if val%2==0:
			dic["even"]+=1
		else:
			dic["odd"]+=1
	if dic["even"]==0:
		print(dic["odd"]-1)
	elif dic["odd"]==0:
		print(0)
	else:
		print(dic["odd"]-1)


for _ in range(eval(input())):
	s = input()
	l = len(s)
	d = dict()
	for x in s:
		if x in d:
			d[x] = d[x] + 1
		else:
			d[x] = 1
	count = 0
	for x in d:
		if d[x]%2 != 0:
			count = count + 1
	if  count < 2 :
		print('0')
	else:
		print(count - 1)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'

def getCount(string):
	cStr = {}
	#oddChar = {}
	for c in string:
		cCount = string.count(c)
		if cCount%2 != 0: 
			cStr[c] = cCount
	sLen = len(string)
	if sLen % 2 == 0 and cStr == {}:
		print(0)
	elif sLen % 2 == 0:
		print(len(cStr) - 1)
	elif sLen % 2 != 0 and cStr == {}:
		print(1)
	else:
		print(len(cStr) -1)

tcNum = int(input())
for i in range(tcNum):
	tcStr = input()
	getCount(tcStr)


def palindrome(str):
	rev = reversed(str)
	if list(str) == list(rev):
		return True
	else:
		return False

def even(n):
	if(n%2 == 0):
		return True
	else:
		return False
	
t = int(input())
for i in range(t):
	s = input();
	if (palindrome(s)):
		print(0)
	else:
		arr = [0]*26
		l = len(s)
		m=0
		for i in range(l):
			n = ord(s[i])-96
			if(not(arr[n])):
				m+=1
			arr[n]+=1
			
		for i in range(26):
			if arr[i]!=0:
				#print i, " ", arr[i], " ", m
				if(even(arr[i])):
					arr[i]=0
					m-=1
		if m==0:
			print(m)
		else:
			print(m-1)
			


from collections import Counter
n=eval(input())

for i in range(0,n):
	sent=list(input())
	count=Counter(sent)
	temp=list(count.values())
	dic={"even":0,"odd":0}
	for val in temp:
		if val%2==0:
			dic["even"]+=1
		else:
			dic["odd"]+=1
	if dic["even"]==0:
		print(dic["odd"]-1)
	elif dic["odd"]==0:
		print(0)
	else:
		print(dic["odd"]-1)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
for t in range(int(input())):
	string = input()
	num = [0 for i in range(26)]
	for s in string:
		num[ord(s)-97]+=1
	total = 0
	odd = False
	for i in num:
		if i%2==1:
			if not odd:
				odd = True
			else:
				total+=1
	print(total)


T = int(input())
for t in range(0, T):
	String = input()
	freq = {}
	for s in String :
		if s in list(freq.keys()) :
			freq[s] += 1
		else :
			freq[s] = 1
	insertion = 0
	one_odd = False
	for key in list(freq.keys()) :
		if freq[key]%2 == 0 :
			continue
		elif freq[key]%2 == 1 and one_odd :
			insertion += 1
		else :
			one_odd = True

	print(insertion)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def solution(st):
	char = {}
	for i in st:
		char[i] = st.count(i)
	if len(st)%2==0:
		c=0
		for i in list(char.values()):
			if i%2!=0:
				c=c+1
		if c>1:
			return c-1
		if c==0:
			return 0
	if len(st)%2!=0:
		co=0
		ce=0
		for i in list(char.values()):
			if i%2!=0:
				co=co+1
		return co-1
t = input()
t=int(t)
s=[]
for i in range(0,t):
	st = input()
	s.append(st)
for i in range(0,t):
	print((solution(s[i])))
	
			
		


alpha2='abcdefghijklmnopqrstuvwxyz'
T=int(input())
while T>0:
	alpha=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
	countOdd=0
	inpString=input()
	for ch in inpString:
		index=alpha2.find(ch)
		if index!=-1:
			alpha[index]=alpha[index]+1
	for i in alpha:
		if i!=0 and i%2!=0:
			countOdd=countOdd+1
	if countOdd==0:
		print(0)
	else:
		print(countOdd-1)
	T=T-1
		


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
import random
t=eval(input())
for i in range(t):
	s=input()
	d={}
	count=0
	for j in s:
		d[j]=0
	for j in s:
		d[j]=d[j]+1
	#print "1"+str(d)              #1
	for j in d:
		d[j]%=2
	#print "2"+str(d)               #2 
	for j in d:
		if d[j]==1:
			d[j]-=1
			break
	#print "3"+str(d)                      #3
	for j in d:
		if d[j]==1:
			count+=1
	#print "4"+str(d)
							 #4
	print(count)