sumit-and-rohil

See Russian Translation

It's a fine sunny afternoon today in California. Looking at the pleasant weather, Sumit is all ready to go out and play with his friend Rohil. Unfortunately, Rohil is down with fever. Seeing that his friend is ill, Sumit decides not to go out - instead play with Rohil inside the house. Sumit loves math, on the contrary Rohil loves strings. Sumit decides to play a game that involves more of strings and less of Maths so that Rohil could be at ease and have fun playing it.

The game is simple and is played on a piece of paper. Sumit writes down a long list of names on that paper and passes it to Rohil. Rohil gets confused on seeing so many names on that paper and asks Sumit about the game. So, Sumit explains him the rules of the game. Rohil is supposed to partition the names into groups, such that:
Each name belongs to exactly one group.
Names that belong to the same group are pairwise anagrams.
The first character of all the names in the same group are equal.
The last character of all the names in the same group are equal.
The number of groups is minimum possible.

Note: Two strings are called anagrams if it's possible to form one string from the other by changing the order of its characters.

Rohil would have won the game easily, if he would have been fit and fine but since he is ill right now he needs your help in winning the game. So, help out Rohil and do give him your blessings.

Input:
The first line contains a single integer N indicating the size of the list. This is followed by N lines where each line contains a name listed by Sumit.  

Output:
In a single line print minimum number of groups in a partition that satisfy above conditions  

Constraints:
1 ≤ N ≤100
1 ≤ Length of a name ≤ 100  

All names will consist of lowercase English alphabets(a-z).

SAMPLE INPUT
6
vinay
vainy
vinit
viint
avinash
aasivnh

SAMPLE OUTPUT
3

Explanation

There are 3 special groups

1)  vinay and vainy 

2)  vinit and viint

3) avinash and aavsinh

Difficulty: EASY
Tags: String algorithms

Implementation

Starter code:

Solutions:
T = eval(input())
names = []
groups = 0

for i in range(T):
	name = str(input())
	names.append(name)

while names:
	temp_name = names.pop(0)
	temp = list()
	temp.append(temp_name)
	matches = [name for name in names if temp_name[0] == name[0] and temp_name[-1] == name[-1]]
	for match in matches:
		temp.append(match)
		names.remove(match)
	
	sort_temp = list()
	for name in temp:
		sort_temp.append(''.join(sorted(name)))
	groups += len(set(sort_temp))	

print(groups)


profiles,total=[],0
for i in range(eval(input())):
	test=input()
	tar=[test[0],test[-1],sorted(test)]
	if tar not in profiles: profiles.append(tar)
print(len(profiles))

#Elegant Piece Of Code 
#StellarCoder


n = input()
# lst =[]
d ={}
for i in range(int(n)):
	s = input()
	a = s[0]+s[-1]

	s =''.join(sorted(s))
	a= a+s

	if a in d:
		d[a] = d[a] +1
	else:
		d[a] =1


print(len(d)) 







listSize = input("")
i = 0
tmp =""
dict1 ={}
while (i < int(listSize)):
	tmp = (input(""))
	if len(tmp) in dict1:
		dict1[len(tmp)] = dict1[len(tmp)] + "," + tmp
	else:
		dict1[len(tmp)] = tmp    
	i+=1
	
	
#print dict1    
	


subgroup1 = 0
tmplist = []
tmplist1 = []

for key in dict1:
	#print "key : %s" %key 
	if "," in dict1[key]:
		a = dict1[key].split(",")
		#print "Value of a is %s" %a
		j = 0
		while j < len(a) :
			k  = j+1
			tmplist = list(a[j])
			tmplist.sort()
			#print "tmplist first loop :%s" %tmplist
			#print "Value of a in first loop is %s" %a
			#print "Value to be matched is %s" %a[j]
			
			while k <  len(a) :
				 tmplist1 = list(a[k])
				 tmplist1.sort()
				 #print "Value to be inside is %s" %a[k]
				 #print "tmplist1 second loop : %s" %tmplist1
				 if ((tmplist == tmplist1) and (a[j][-1] == a[k][-1]) and (a[j][0] == a[k][0])):
					 a.remove(a[k])
					 k = k - 1
					 if j > 0 :
						 j-=1
					 #print "j is %s" %j    
					 
					 #print " Value to be deleted inside is %s" %a[k]
					 #print "Value of a in second loop is %s" %a
					 #print "Wah kya baat hai" 
   
				 k+=1
   
			subgroup1+=1

			#print " Value to be deleted is %s" %a[j]
					  
			a.remove(a[j])    
			

			#print "Value of subgroup at this point of time is %s" %subgroup1 
	else:
	   subgroup1+=1 
				
					 
print(subgroup1)
#print dict1  

  
	


listSize = input("")
i = 0
tmp =""
dict1 ={}
while (i < int(listSize)):
	tmp = (input(""))
	if len(tmp) in dict1:
		dict1[len(tmp)] = dict1[len(tmp)] + "," + tmp
	else:
		dict1[len(tmp)] = tmp    
	i+=1
	
	
#print dict1    
	

subgroup = 0
subgroup1 = 0
rajababu = 0
tmplist = []
tmplist1 = []

for key in dict1:
	#print "key : %s" %key
	j = 0  
	if "," in dict1[key]:
		a = dict1[key].split(",")
		#print "Value of a is %s" %a
		length = len(a)
		while j < len(a) :
			rajababu = 0
			k  = 1
			tmplist = list(a[j])
			tmplist.sort()
			#print "tmplist first loop :%s" %tmplist
			#print "Value of a in first loop is %s" %a
			
			while k <  len(a) :
				 tmplist1 = list(a[k])
				 tmplist1.sort()
				 #print "tmplist1 second loop : %s" %tmplist1
				 if ((tmplist == tmplist1) and (a[j][-1] == a[k][-1]) and (a[j][0] == a[k][0])):
					 subgroup = 1
					 rajababu = 1
					 a.remove(a[k])
					 k = k - 1
					 #print "j is %s" %j
					 if j > 0 :
						 j-=1
					 #print "j is %s" %j    
					
					 #print " Value to be deleted inside is %s" %a[k]
					 #print "Value of a in second loop is %s" %a
					 #print "Wah kya baat hai" 
   
				 k+=1
			if rajababu == 0:
				subgroup1+=1
			else:   
				subgroup1+=subgroup
			#print " Value to be deleted is %s" %a[j]
					  
			a.remove(a[j])    
			

			#print "Value of subgroup at this point of time is %s" %subgroup1 
	else:
	   subgroup1+=1 
				
					 
print(subgroup1)
#print dict1  


N = int(input())
grp = [input()]
for i in range(N-1):
	inp = input()
	for w in grp:
		isAnag = True
		lw=len(w)
		li=len(inp)
		if lw!=li:
			isAnag = False
			continue
		elif w[0]!=inp[0]:
			isAnag = False
			continue		
		elif w[lw-1]!=inp[li-1]:
			isAnag = False
			continue
		else:
			arr=[0]*26
			for i in range(lw):
				#print ord(w[i])-ord('a')
				#print ord(inp[i])-ord('a')
				arr[ord(w[i])-ord('a')]=1+arr[ord(w[i])-ord('a')]
				arr[ord(inp[i])-ord('a')]=arr[ord(inp[i])-ord('a')]-1
			for i in arr:
				if i!=0:
					isAnag = False
					break
		if isAnag:
			break
				
	if not isAnag:
		grp.append(inp)

print(len(grp))		


n=eval(input())
group=set()
for i in range(n):
	list1=[]
	name = input()
	list1.append(name[0])
	list1.append(name[-1])
	if len(name)>2:
		list1=list1+sorted(name[1:-1])
	group.add(''.join(list1))
print(len(group))


#!/usr/bin/python
def anagramOrNot(a,b):
	if len(a)!=len(b):
		return False
	for i in a:
		if (i not in b) or b.count(i)!=a.count(i):
			return False
	for i in b:
		if (i not in a) or b.count(i)!=a.count(i):
			return False
	return True

def firstAndLast(a,b):
	if a[0]==b[0] and a[-1]==b[-1]:
		return True
	else:
		return False

def process(a,groupList):
	for word in groupList:
		if anagramOrNot(a,word) and firstAndLast(a,word):
			return True
	return False

number = int(eval(input()))
l=[]
for i in range(0,number):
	test = input()
	l.append(test)
groupList = []
# print l
for word in l:
	if process(word,groupList):
		pass
	else:
		groupList.append(word)
# print groupList
print(len(groupList))


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

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

def getNumbers(s):
	l=[0]*26;
	for v in s:
		l[ord(v)-ord('a')]+=1
	return tuple(l)	
		
def makeKey(s):
	return (s[0],s[-1],getNumbers(s))

n=eval(input())
names=dict()
for i in range(n):
	s=input()
	t=makeKey(s)
	if t in names: names[t]+=1
	else: names[t]=1

print(len(list(names.keys())))


def strtend(str1, str2):
	if str1[0] == str2[0] and str1[-1] == str2[-1]:
		return True
	else:
		return False
		
def isanag(str1, str2):
	alist1 = list(str1)
	alist2 = list(str2)
	
	alist1.sort()
	alist2.sort()
	
	pos = 0
	matches = True
	
	while pos < len(str1) and matches:
		if alist1[pos]==alist2[pos]:
			pos = pos + 1
		else:
			matches = False
	return matches

n = int(input())
names = list()
for i in range(n):
	names.append(input().rstrip())


grno = 0
temp_grp = list()

while len(names) != 0:
	buff = list()
	str1 = names[0]
	
	for i in range(1, len(names)):
		if strtend(str1, names[i]):
			buff.append(names[i])
	
	for i in range(len(buff)):
		names.remove(buff[i])
	
	buff.append(str1)
	names.remove(str1)
	
	temp_grp.append(buff)

buff = list()
final_grp = list()

for grp in temp_grp:
	while len(grp) != 0:
		buff = list()
		str1 = grp[0]
		for i in range(1, len(grp)):
			if isanag(str1, grp[i]):
				buff.append(grp[i])
			
		for i in range(len(buff)):
			grp.remove(buff[i])
		
		buff.append(str1)
		grp.remove(str1)
		
		final_grp.append(buff)
# 		print grp
# 		print buff
# 		print final_grp
# 		print

# print final_grp
print(len(final_grp))
	


count =0
l=[]
for _ in range(eval(input())):
	a= input()
	l.append(a)
for x in range(len(l)):
	s=l[x][1:len(l[x])-1]
	p= list(sorted(s))
	p= "".join(p)
	l[x]=l[x].replace(s,p)
s=set(l)
print(len(s))






import sys

n = sys.stdin.readline()
names = [name.rstrip() for name in sys.stdin.readlines()]
converted_names = [n[0] + ''.join(sorted(n[1:-1])) + n[-1] for n in names]
print(len(set(converted_names)))


def name_sort(name):
	y=list(name)
	yy=y[1:(len(name)-1)]
	yy.sort()
	z=[]
	z.append(name[0])
	z=z + yy
	z.append(name[len(name)-1])
	return z

def count_groups():
	num_names=eval(input(""));
	names=[]
	group = 0
	for i in range(num_names):
		names.append(input())
	group = num_names
	#print " the list size is " + str(len(names))
	for i in range(num_names):
		name=names[i]
		if names[i] != "":
			name_list = name_sort(names[i])
			for j in range(i+1,len(names)):
				if names[j] != "":
					new_list = name_sort(names[j])
					var = cmp(name_list,new_list)
					if  var == 0 :
						names[j]=""
						group = group-1
	print(group)

count_groups()
	


def checkIfTwoStringsAreAnagrams(str1,str2):
	str1List=[character for character in str1 ]
	str2List=[character for character in str2 ]

	for character in str2List:
		 if character not in str1List:
			 return False
		 else:
			 str1List.remove(character)

	if not str1List:
		return True
	else:
		return False



N=int(input())

names=[input() for x in range(0,N)]
solDict={}

for name in names:
	key=name[0]+name[-1]
	list=solDict.get(key,[])
	list.append(name)
	solDict[key]=list


inputStack=[]
processedStack=[]


for value in solDict.values():
	inputStack.append(value)

while (inputStack):
	group=inputStack.pop()
	firstString=group[0]
	notAnagramsWithFirstString=[]
	tempList=[x for x in group]
	for entry in tempList:
		if  not checkIfTwoStringsAreAnagrams(firstString,entry):
			group.remove(entry)
			notAnagramsWithFirstString.append(entry)
	if notAnagramsWithFirstString:
		inputStack.append(notAnagramsWithFirstString)

	processedStack.append(group)

print(len(processedStack))






import operator
from functools import reduce
n=eval(input())
group=set()
for i in range(n):
	list1=[]
	name = input()
	list1.append(name[0])
	list1.append(name[-1])
	if len(name)>2:
		list1=list1+sorted(name[1:-1])
	group.add(reduce(operator.add,list1))
print(len(group))


def letsee(name):
	l=len(name)
	s=name[0]
	e=name[l-1]
	t=sorted(name)
	return {"length":l,"start":s,"end":e,"alpha":t}

group=[]

N1=int(input())
for j in range(N1):
	abc=input()
	d=letsee(abc)
	if d not in group:
	    group.append(d)
print(len(group))
			


n=eval(input())
l=[]
for i in range(0,n):
	s=input()
	temp=[]
	length=len(s)
	for j in range(0,length):
		temp.append(s[j])
	temp.sort()
	l.append([s[0],s[length-1],temp])
l.sort()
l.append('*')
i=0
count=0
groups=0
while i<n:
	if l[i]==l[i+1]:
		count+=1
		i+=1
	else:
		count=0
		groups+=1
		i+=1
print(groups)
	


def main():
	n=input()
	li=[]
	for i in range(0,int(n)):
		stri=input()
		li.append(stri)
	li2=[]	
	for i in li:
		out=(sorted(i[1:-1]))
		stri=''.join(i for i in out)
		stri=i[0]+stri+i[-1]
		li2.append(stri)
	print(len(list(set(li2))))
if __name__=='__main__':
	main()


num_cases = int(input().rstrip("\n"))
d = {}
for count in range(num_cases):
	input = input().rstrip("\n")
	key = input[0] + "".join(sorted(input[1:len(input) - 1])) + input[len(input) - 1]
	if d.__contains__(key):
		value = d[key]
		value.append(input)
		d[key] = value
	else:
	    d[key] = [input]
count = 0
print(len(d))


'''
# 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!'
arr = []
no = int(input())
for i in range(no):
	strInput = input()
	firstChar = strInput[0]
	lastChar = strInput[-1]
	sortedStrInput = "".join(sorted(strInput))
	elem = [sortedStrInput, firstChar, lastChar]
	if elem not in arr:
		arr.append(elem)
		
print(len(arr))




count =0
l=[]
for _ in range(eval(input())):
	a= input()
	l.append(a)
for x in range(len(l)):
	s=l[x][1:len(l[x])-1]
	p= list(sorted(s))
	p= "".join(p)
	l[x]=l[x].replace(s,p)
s=set(l)
print(len(s))






def name_sort(name):
	y=list(name)
	yy=y[1:(len(name)-1)]
	yy.sort()
	z=[]
	z.append(name[0])
	z=z + yy
	z.append(name[len(name)-1])
	return z

def count_groups():
	num_names=eval(input(""));
	#num_names=0
	#print "enter the names"
	names=[]
	group = 0
	#f = open('input.txt', 'r')
	for i in range(num_names):
		names.append(input())
	#for line in f:
	#    line.rstrip('\n')
	#    names.append(line)
	#    num_names = num_names + 1
	group = num_names
	#print " the list size is " + str(len(names))
	for i in range(num_names):
		name=names[i]
		if names[i] != "":
			flag=0
			name_list = name_sort(names[i])
			for j in range(i+1,len(names)):
				if names[j] != "":
					new_list = name_sort(names[j])
					var = cmp(name_list,new_list)
					if  var == 0 :
						names[j]=""
						group = group-1
						flag = 1;
	print(group)

count_groups()
	


def add(s,dc):
	k=list(dc.keys())
	f=1
	for i in range(len(k)):
		s1=k[i]
		if sorted(s1)==sorted(s) and s1[0]==s[0] and s1[len(s1)-1]==s[len(s)-1]:
			dc[k[i]]=s
			f=0
			break
	if f==1:
		dc[s]=''
n=int(eval(input()))
dc={}
while n>0:
	s=input()
	add(s,dc)
	n=n-1
print(len(dc))


l = []
for _ in range(int(input())):
	s = input()
	flag = 0
	for i in l:
		if (sorted(s) == sorted(i)) and (s[:1]==i[:1]) and (s[len(s)-1:]==i[len(i)-1:]):
			flag = 1
			break
	if flag == 0:
		l.append(s)
print(len(l))
#print l


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

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
N=int(input())
word=[]
first=[]
last=[]
length=[]
for i in range(N):
	a=input().strip()
	word.append(a)
	first.append(a[0])
	last.append(a[-1])
	length.append(len(a))
group={}
group_no=0
for j in range(N):
	count_1=0
	for w in group:
		for aa in group[w]:
			if word[j] in aa:
				count_1+=1
	if count_1==0:
		for k in range(j+1,N):
			if first[j]==first[k]:
				if last[j]==last[k]:
					if length[j]==length[k]:
						count=0
						a=word[j]
						b=word[k]
						a1=list(map(ord,a))
						b1=list(map(ord,b))
						a1.sort()
						b1.sort()
						for i in range(len(a1)):
							if a1[i]==b1[i]:
								count+=1
							if count==len(a1):
								cou=0
								for ll in group:
									if a in group[ll]:
										cou+=1
										bb=ll
								if cou==1:
									group[bb].append(b)
								else:
									group[group_no]=[]
									group[group_no].append(a)
									group[group_no].append(b)
									group_no+=1
sum=0
for m in group:
	sum+=len(group[m])
print(len(group)+N-sum)
							
						



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

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
n=int(input())
l=[]
for i in range(n):
	l.append(input())
	
for i in range(n):
	s=l[i][1:len(l[i])-1]
	s_list=list(s)
	s_list.sort()
	s_sort="".join(s_list)
	l[i]=l[i].replace(s,s_sort)
	
l.sort()
l=set(l)
print(len(l))


List1 = []
for i in range(int(input())):
	List1.append(input())

count=0
for p in range(len(List1)):
	str1 = List1.pop()
	if str1 != '':
		count +=1
		for x in range(len(List1)):
			if (List1[x][0:1] == str1[0:1]) and (List1[x][len(List1[x])-1:] == str1[len(str1)-1:]):
				if sorted(List1[x]) == sorted(str1):
					List1[x] = ""
print (count)






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

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

def h(s):
	return s[0]+s[-1]+''.join(sorted(list(s)))

N = int(input())
_set = set()
for _ in range(N):
	s = input()
	_set.add(h(s))
print(len(_set))


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

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
words=[]
hash=dict()
no_group=0
k=int(input())
for i in range(k):
	s=input();
	words.append(s)
for i in range(k):
	if words[i] not in hash:
		no_group += 1
		for j in range(i+1,k):
			len1=len(words[i])
			len2=len(words[j])
			if (len1 == len2) and (words[i][0] == words[j][0]) and words[j][len2 - 1] == words[i][len1 - 1]:
				s=''.join(sorted(words[i]))
				s1=''.join(sorted(words[j]))
				if(s==s1):
					hash[words[j]]=1
					continue
		hash[words[i]]=1
print(no_group)