primestring

Alice has just learnt about primeStrings. A string is a primeString if the number of distinct alphabets used in the string is a prime and also the number of occurrences of each alphabet in the string is also a prime.
Given a String you need to tell if it is a primeString or not.

Input:
First line contains T which is the number of test cases.
T lines follow each containing a string of characters 'a' to 'z'.

Output:
For each input, output "YES" if the number is a primeString or "NO" if not.

Constraints:

1 ≤ T ≤ 10
 1 ≤ Length\; of\; string ≤ 10^5

Scoring:

1 ≤ T ≤ 10, 1 ≤ Length\; of\; string  ≤ 10\; (20 pts)
1 ≤ T ≤ 10, 1 ≤ Length\; of\; string  ≤ 1000 \;(30 pts)
1 ≤ T ≤ 10, 1 ≤ Length\; of\; string  ≤ 10^5 (50 pts)

SAMPLE INPUT
3
ababb
abcab
aabbccdd

SAMPLE OUTPUT
YES
NO
NO

Explanation

Case 1: 2 different alphabets each occurring 2 and 3 times respectively so string "ababb" is a PrimeString.   

Case 2: In second string char 'a' occurs 2 times, char 'b' occurs 2 times but char 'c' occur only 1 time which is not a prime number that's why string "abcab" is not a PrimeString.  

Case 3: String contains 4 distinct alphabets and 4 is not a prime Number so the string "aabbccdd" is not a PrimeString.

Difficulty: EASY
Tags: Fundamentals

Implementation

Ad-hoc

Starter code:

Solutions:
def prime1(no):
	cnt2 = 0
	if no == 1:
		return False
	for i in range(2,no):
		if no % i == 0:
	  cnt2 = 1
	if no == 2 or cnt2 == 0:
		return True
	else:
		return False
		
tc=eval(input())
if tc>=1 and tc<=10:
		for j in range(0, tc):
			ret_val = 0
			M = input()
			if len(M)>=1 and len(M)<=100000:
				b = set(M)
				flag = 1
				if not prime1(len(b)):
					flag = 0
				for i in set(b):
					if not prime1(M.count(str(i))):
					  flag = 0
				if flag == 1:
					print("YES")
				else:
					print("NO")


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

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
from collections import Counter
import math;
#print 'Hello World!'
def prime(no):
	i=2;
	if(no==1 ):
		return 1;
	
	#print("in l1");
	while(i <=math.sqrt(no)):
		#print("in l1", i, " no:",no);
		if(no%i==0):
			#print("1", i, " no:",no);
			return 1;
		i=i+1;
	return 0;
no=int(input());

while(no >0):
	cnt=0;
	strj=input();
	count = Counter(strj)
	a=len(set(strj));
	if(prime(a)==1):
		print("NO");
	else:
		flag=1;
		for  i in set(strj):
			a=count[i];
			#print("freq: %s and letter %s",a,i);
			if(prime(a)==1):
				print("NO");
				flag=0;
				break;
		#print("cnt :",cnt)
		if(flag==1):
			print("YES");
	no=no-1;
	
		
		


def isNumPrime(num):
	if num > 1:
		for i in range(2, num):
			if (num % i) == 0:
				return False
		else:
			return True
	else:
		return False
	   


def isStringPrime(string):
	dict = {}
	for c in string:
		if c in dict:
			dict[c] += 1
		else:
			dict[c] = 1
	
	if isNumPrime(len(dict)) is False:
		return False
	
	for value in list(dict.values()):
		if isNumPrime(value) is False:
			return False
	
	return True


if __name__ == '__main__':

	t = int(input())
	for i in range(t):
		string = input()
		if isStringPrime(string):
			print('YES')
		else:
			print('NO')



def foo(string):
	freq = {}

	for char in string:
		freq.setdefault(char, 0)
		freq[char] += 1

	AllPrime = True

	if isPrime(len(freq)):
		for i in list(freq.values()):
			if isPrime(i):
				continue
			else:
				AllPrime = False
				break
		if AllPrime:
			return 'YES'
		else:
			return 'NO'
	else:
		return 'NO'

def isPrime(n):
	if n == 2:
		return True
	elif 2 ** (n-1) % n == 1:
		return True
	else:
		return False

T = int(input())
for tc in range(T):
	string = input().strip()
	print(foo(string))




import math

array = [0]

def calculate_primes(num):
	global array
	array = (num+1)*[0]
	lim = int(math.sqrt(num))
	for i in range(2,lim):
		j = i*i
		if not array[j]:
			while(j < num):
				array[j] = 1
				j = j + i
	array[0] = 1
	array[1] = 1
	return

		
def isPrime(num):
	return not array[num]

if __name__ == "__main__":
	calculate_primes(100000)
	t = eval(input())	
	while t > 0:
		string = input()
		count = {}
		for i in string:
			if i not in count:
				count[i] = 0
			count[i] = count[i] + 1
		distinct = len(list(count.keys()))
		indiv_vals = [count[i] for i in count]
		result = True
		#print distinct, indiv_vals
		if isPrime(distinct):
			for i in indiv_vals:
				if not isPrime(i):
					result = False
					break
		else:
			result = False
		if result:
			print("YES")
		else:
			print("NO")
		t = t - 1
		


def prime1(no):
	cnt2 = 0
	if no == 1:
		return False
	for i in range(2,no):
		if no % i == 0:
	  cnt2 = 1
	if no == 2 or cnt2 == 0:
		return True
	else:
		return False
		
tc=eval(input())
if tc>=1 and tc<=10:
		for j in range(0, tc):
			ret_val = 0
			M = input()
			if len(M)>=1 and len(M)<=100000:
				b = set(M)
				flag = 1
				if not prime1(len(b)):
					flag = 0
				for i in set(b):
					if not prime1(M.count(str(i))):
					  flag = 0
					  break
				if flag == 1:
					print("YES")
				else:
					print("NO")


def prime1(no):
	cnt2 = 0
	if no == 1:
		return False
	for i in range(2,no):
		if no % i == 0:
	  cnt2 = 1
	if no == 2 or cnt2 == 0:
		return True
	else:
		return False
		
tc=eval(input())
if tc>=1 and tc<=10:
		for j in range(0, tc):
			ret_val = 0
			M = input()
			if len(M)>=1 and len(M)<=100000:
				b = set(M)
				flag = 1
				if not prime1(len(b)):
					flag = 0
				for i in set(b):
					if not prime1(M.count(str(i))):
					  flag = 0
				if flag == 1:
					print("YES")
				else:
					print("NO")


def isprime(n):
	n = abs(int(n))
	if n < 2:
		return False
	if n == 2: 
		return True   
	if not n & 1: 
		return False
	for x in range(3, int(n**0.5) + 1, 2):
		if n % x == 0:
			return False

	return True
t=eval(input())
for i in range(t):
	s=input()
	l=list()
	for j in s:
		l.append(j)
	d=dict()
	for k in l:
		d[k]=d.get(k,0)+1
	m=len(d)
	if(isprime(m)):
		flag=0
		for a,b in list(d.items()):
			g=isprime(b)
			if(g==False):
				flag=1
				break
		if flag==0:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


from collections import Counter
n = 100001


def mysieve(n):
	for i in range(2, n):
		if i * i <= n and not prime[i]:
			for j in range(i * i, n, i):
				prime[j] = 1


prime = [0] * n
prime[1] = 1
mysieve(n)
for i in range(eval(input())):
	res = "YES"
	string = Counter(input())
	if prime[len(string)] == 0:
		for val in string:
			
			if prime[string[val]]:
				res = "NO"
				break
	else:
		res = "NO"
	print(res)


import math
for i in range(eval(input())):
	l=[]
	a=input()
	d=0
	e=0
	freq=[0 for _ in range(26)]
	for c in a:
		freq[ord(c)-ord('a')]+=1
	for j in range(0,len(a)):
		if(a[j] not in l):
			l.append(a[j])
	h=len(l)
	if(len(l)==1):
		d+=1
	for k in range(2,int(math.sqrt(h))+1):
		if(h%k==0):
			d+=1
	for m in range(0,len(freq)):
		if(freq[m]!=0):
			if(freq[m]==1):
				e+=1
			else:
				for n in range(2,int(math.sqrt(freq[m]))+1):
					if(freq[m]%n==0):
						e+=1
	if(d>0 or e>0):
		print("NO")
	else:
		print("YES")


from collections import OrderedDict
for i in range(eval(input())):
	a=input()
	b=''.join(OrderedDict.fromkeys(a))
	c=len(b)
	f1=0
	f2=0
	if c==1:
		f1=1
	else:
		for i in range(2,int(c**0.5)+1):
			if c%i==0:
				f1=1
				break
		for j in range(c):
			x=a.count(b[j])
			if x==1:
				f2=1
				break
			else:
				for k in range(2,int(x**0.5)+1):
					if x%k==0:
						f2=1
	if f1==0 and f2==0:
		print("YES")
	else:
		print("NO")
				



def is_Prime(n):
	if n==2 or n==3: return True
	if n%2==0 or n<2: return False
	for i in range(3,int(n**0.5)+1,2):   # only odd numbers
		if n%i==0:
			return False

	return True
def get_input():
	case = eval(input())
	if case in range(1,11):
		for i in range(case):
			decide = True
			string = input()
			string = list(string)
			set_string = list(set(string))
			dist_alpha = is_Prime(len(set_string))
			for a in set_string:
				var = is_Prime(string.count(a))
				decide = dist_alpha and decide and var
			if decide:
				print("YES")
			else:
				print("NO")
	else:
		exit
get_input()


def ip(n):
	'''check if integer n is a prime'''
	# make sure n is a positive integer
	#n = abs(int(n))
	# 0 and 1 are not primes
	if n < 2:
		return False
	# 2 is the only even prime number
	if n == 2: 
		return True    
	# all other even numbers are not primes
	if not n & 1: 
		return False
	# range starts with 3 and only needs to go up the squareroot of n
	# for all odd numbers
	for x in range(3, int(n**0.5)+1, 2):
		if n % x == 0:
			return False
	return True
for _ in range(eval(input())):
	s=input().strip()
	d={}
	for c in s:
		if c not in d:
			d[c]=1
		else:
			d[c]+=1
	l=len(d)
	#print l,d
	if not ip(l):
		print("NO")
	else:
		for k in d:
			if not ip(d[k]):
				print("NO")
				break
		else:
			print("YES")


def getres(s):
	dic = {}
	temp = 0
	for mem in s:
		if mem in dic:
			dic[mem] = dic[mem]+1
		else:
			dic[mem] = 1
	#print dic
	ld = len(dic)
	#print ld
	if isprime(ld) == 1:
		for mem1 in dic:
			if isprime(dic[mem1]) == 1:
				pass
			else:
				temp = 1
				break
		if temp == 1:
			print("NO")
		else:
			print("YES")
	else:
		print("NO")

def isprime(a):
	if a ==1 :
		return 0
	if a == 2:
		return 1
	else:
		for mem in range(2,int(a**0.5)+1):
			#print mem
			if a% mem == 0:
				return 0
			else:
				pass
		else:
			return 1




t = int(input())
for mem in range(t):
	s = str(input())
	getres(s)
#	n = int(raw_input())
#	print isprime(n)


def prime1(no):
	cnt2 = 0
	if no == 1:
		return False
	for i in range(2,no):
		if no % i == 0:
	  cnt2 = 1
	if no == 2 or cnt2 == 0:
		return True
	else:
		return False
		
tc=eval(input())
if tc>=1 and tc<=10:
		for j in range(0, tc):
			M = input()
			if len(M)>=1 and len(M)<=100000:
				b = set(M)
				flag = 1
				if not prime1(len(b)):
					flag = 0
					
				for i in set(b):
					if not prime1(M.count(str(i))):
					  flag = 0
				if flag == 1:
					print("YES")
				else:
					print("NO")


def prime1(no):
	cnt2 = 0
	if no == 1:
		return False
	for i in range(2,no):
		if no % i == 0:
	  cnt2 = 1
	if no == 2 or cnt2 == 0:
		return True
	else:
		return False
		
tc=eval(input())
if tc>=1 and tc<=10:
		for j in range(0, tc):
			ret_val = 0
			M = input()
			if len(M)>=1 and len(M)<=100000:
				b = set(M)
				flag = 1
				if not prime1(len(b)):
					flag = 0
				for i in set(b):
					if not prime1(M.count(str(i))):
					  flag = 0
				if flag == 1:
					print("YES")
				else:
					print("NO")


prime=[1]*(100000+1)
i=2
n=100000
prime1=[]
while i*i<=n:
	if prime[i]==1:
		j=i*2
		while j<=n:
			if prime[j]==1:
				prime[j]=0
			j+=i
	i=i+1
mod=pow(10,9)+7
for i in range(2,n+1):
	if prime[i]==1:
		prime1.append(i)
t=eval(input())
while t>0:
	t=t-1
	a=input()
	a=list(a)
	a.sort()
	b=set(a)
	f=0
	if len(b) in prime1:
		i=0
		while i<len(a):
			if a.count(a[i]) in prime1:
				i=i+a.count(a[i])
				continue
			else:
				f=1
				print('NO')
				break
	else:
		f=1
		print('NO')
	if f==0:
		print('YES')


from collections import Counter

def primecheck(n):
	return all(n % i for i in range(2, n))

def check(string):
	counter = Counter(string)
	
	if primecheck(len(set(string))) == 1 and len(set(string)) != 1:
		for i in set(string):
			if primecheck(counter[i]) == 0 or counter[i] == 1:
				return "NO"
		return "YES"
	return "NO"

n = eval(input(""))
for i in range(n):
	string = input("")
	print(check(string))
	


from math import sqrt
from itertools import count, islice
tc=eval(input())
def isPrime(n):
	if n < 2: return False
	for number in islice(count(2), int(sqrt(n)-1)):
		if not n%number:
			return False
	return True
	
for i in range(tc):
	string=input()
	if isPrime(len(list(set(string)))):
			st_count=0
			for i in list(set(string)):
				if isPrime(string.count(i)):
					st_count+=1
				else:
					st_count=st_count
			if st_count==len(list(set(string))):
				print("YES")
			else:
				print("NO")
	else:
		print("NO")


'''
# 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
def prime(n):
	c=0
	if n==1 or n==0:
		return 0
	for i in range(2,n):
		if n%i==0:
			return 0
		c+=1
	else :
		return 1
t=int(input())
while t>0:
	t-=1
	s=input()
	s=list(s)
	c=Counter(s)
	m=0
	for key in c:
		m+=prime(c[key])
	if m==len(c) and prime(m)==1:
		print("YES")
	else:
		print("NO")


from math import *
testcase=input()
testcase=int(testcase);
def isprime(number):
	if number==0 or number==1:
	  return 0;
	else:
	  for i in range (2,number):
	   if ( number % i == 0 and i != number ):
		 return 0;
	  return 1;
while (testcase>0):
	string=input()
	count=[];
	discount=0;
	flag=1;
	for i in range(0,26):
		count.append(0);
	for i in range(0,len(string)):
		var=ord(string[i])-97;
		count[var]=count[var]+1;
	for i in range(0,26):
		if count[i]!=0:
			discount=discount+1;
			if (isprime(count[i])==0):
				flag=0;
				break;
	if (flag and isprime(discount)):
		print("YES")
	else:
		print("NO")
	testcase=testcase-1;


def is_prime(n):
	if n < 2:
		return False
	for d in range(2, n/2 + 1):
		if n%d == 0:
			return False
	return True

def main():
	t = int(input())
	for i in range(t):
		count_list = [0 for i in range(0, 26)]
		s = input()
		for c in s:
			count_list[ord(c) - ord('a')] += 1
		count_list = [e for e in count_list if e != 0]
		if not is_prime(len(count_list)):
			print("NO")
		else:
			flag = False
			for count in count_list:
				if not is_prime(count):
					print("NO")
					flag = True
					break

			if not flag:
				print("YES")

if __name__ == "__main__":
	main()


def is_prime(n):
	for i in range(3, n):
		if n % i == 0:
			return False
	if n==1 or n==4:
		return False
	return True	
t = int(input())
while t>0:
	n = input()
	list = [ord(i)-97 for i in n]
	t = t-1
	a=[0]*26
	for i in list:
		a[i]=a[i]+1
	x = 0
	m = 0
	for i in a:
		if i!=0:
			x=x+1
			if is_prime(i)!=True:
				break
	else:
		m = 1
	if is_prime(x) and m==1:
		print("YES")
	else:
		print("NO")
		


import math
def primeSieve(no):
	sieveSize=no+1
	sieve = [True] * sieveSize
	sieve[0] = False
	sieve[1] = False
	for i in range(2, int(math.sqrt(sieveSize)) + 1):
		pointer = i * 2
		while pointer < sieveSize:
			sieve[pointer] = False
			pointer += i
	primes = []
	for i in range(sieveSize):
		if sieve[i] == True:
			primes.append(i)
	if no in primes:
		return True
	else:
		return False
# print len(primeSieve(int(raw_input())))


for x in range(int(input())):
	string=input()
	d=dict()
	for c in string:
		if c not in d:
			d[c]=1
		else:
			d[c]+=1
	key_len=len(list(d.keys()))
	distinct_check=primeSieve(key_len)
	# print distinct_check
	no_check=False
	for s in list(d.values()):
		if primeSieve(s) is False:
			no_check=False
			break
		else:
			no_check=True
	if distinct_check and no_check:
		print('YES')
	else:
		print('NO')



def prime1(no):
	cnt2 = 0
	if no == 1:
		return False
	for i in range(2,no):
		if no % i == 0:
	  cnt2 = 1
	if no == 2 or cnt2 == 0:
		return True
	else:
		return False
		
tc=eval(input())
if tc>=1 and tc<=10:
		for j in range(0, tc):
			ret_val = 0
			M = input()
			if len(M)>=1 and len(M)<=100000:
				b = set(M)
				flag = 1
				if not prime1(len(b)):
					flag = 0
				else:	
					for i in set(b):
					if not prime1(M.count(str(i))):
					  flag = 0
				if flag == 1:
					print("YES")
				else:
					print("NO")


def prime1(no):
	cnt2 = 0
	if no == 1:
		return False
	for i in range(2,no):
		if no % i == 0:
	  cnt2 = 1
	if no == 2 or cnt2 == 0:
		return True
	else:
		return False
		
tc=eval(input())
if tc>=1 and tc<=10:
		for j in range(0, tc):
			M = input()
			if len(M)>=1 and len(M)<=100000:
				b = set(M)
				flag = 1
				if not prime1(len(b)):
					flag = 0
					
				for i in set(b):
					if not prime1(M.count(str(i))):
					  flag = 0
				if flag == 1:
					print("YES")
				else:
					print("NO")


def primes(n): # sieve of eratosthenes
	ps, sieve = [2], [True] * (n + 1)
	for p in range(3, n + 1,2):
		if sieve[p]:
		   ps.append(p)
		   for i in range(p * p, n + 1, p):
			   sieve[i] = False
	return ps
def strprime(a):
	k=0
	for i in set(a):
		p= a.count(i)
		if p not in s:
			k=1
			break
		else:
			continue
	return k
for _ in range(eval(input())):
	a= input()

	s= list(primes(len(a)))
	r= len(set(a))
	if r not in s:
		print("NO")
	elif strprime(a):
		print("NO")
	else:
		print("YES")
	



from math import sqrt
def sieve(n):
	primes=list(range(3,n+1,2))
	for base in range(len(primes)):
		if primes[base]==None:
			continue
		if primes[base]>sqrt(n):
			break
		
		for i in range(base+(base+1)*primes[base],len(primes),primes[base]):
			primes[i]=None
			
	primes.insert(0,2)
	return [_f for _f in primes if _f]
	
	
primes=sieve(100000)

def prime(n):
	if n in primes:
		return True
	return False

for _ in range(eval(input())):
	arr=[0]*26
	string=list(input())
	k=1
	if prime(len(list(set(string)))):
		for item in string:
			arr[ord(item)-97]+=1
			

		for item in arr:
			if item>0:
				if prime(item)==False:
					print("NO")
					k=5
					break
		if k==1:
			print("YES")
		
		
	else:
		print("NO")
	



prime={}
for i in range(0,100001):
	prime.update({i:0})
prime.update({0:1})
prime.update({1:1})

for i in range(4,100004,2):
	prime.update({i:1})
for i in range(3,100004,2):
	if i*i>100004:
		break
	if (prime[i])==0:
		for j in range(2,100004,1):
			if i*j>100004:
				break
			prime[i*j]=1
t=int(input())
for i in range(t):
	mp={};
	k=0
	for j in range(26):
		mp[j]=0
	str=input()
	l=len(str)
	for j in range(l):
		p=ord(str[j])-97
		if mp[p] == 0:
			k+=1
		mp[p]+=1
	#print "e"
	if prime[k]==0:
		counter=0
		#print "hello"
		for j in range(26):
			if mp[j] !=0:
				if prime[mp[j]]==0:
					continue
				else:
					counter=1
					break
		if counter==0:
			print("YES")
		else:
			print("NO")
	else:
		print("NO")


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

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
from collections import Counter
import string
from math import sqrt

def check_prime(n):
	if n<2:
		return False
	if n%2==0:
		return n==2
	if n%3==0:
		return n==3
	if n%5==0:
		return n==5
	for i in range(7, int(sqrt(n))+1, 2):
		if n%i == 0:
			return False
	return True

def count_letters(word):
	i=0
   	count=0
   	flag=0
   	j=len(word)
   	while(i<j):
   		b=word.count(word[i])
			i=i+b
		count=count+1;
		tmp=check_prime(b)
	  		if(tmp==False) :
			flag=1
			break
   	k=check_prime(count)
   	if(k==False) :
		flag=1  
   	if(flag==1) :
		print('NO')
   	if(flag==0) :
		print('YES')
t=eval(input())
d=0
if t>10 :
	print("Error in giving number of test cases should be between 1 and 10")
elif t<1:
	print("Error in giving number of test cases should be between 1 and 10")
else :
		while(d<t):       
		word = input();
			if(len(word)<1):
			print("Error in giving length of string,should be between 1 and 10^5")
			break
		elif(len(word)>100000):
			print("Error in giving length of string,should be between 1 and 10^5")
			break
		b=sorted(word)
		count_letters(b)
  		d=d+1