Let's call a string $s$ perfectly balanced if for all possible triplets $(t,u,v)$ such that $t$ is a non-empty substring of $s$ and $u$ and $v$ are characters present in $s$, the difference between the frequencies of $u$ and $v$ in $t$ is not more than $1$.

For example, the strings "aba" and "abc" are perfectly balanced but "abb" is not because for the triplet ("bb",'a','b'), the condition is not satisfied.

You are given a string $s$ consisting of lowercase English letters only. Your task is to determine whether $s$ is perfectly balanced or not.

A string $b$ is called a substring of another string $a$ if $b$ can be obtained by deleting some characters (possibly $0$) from the start and some characters (possibly $0$) from the end of $a$.


-----Input-----

The first line of input contains a single integer $t$ ($1\leq t\leq 2\cdot 10^4$) denoting the number of testcases.

Each of the next $t$ lines contain a single string $s$ ($1\leq |s|\leq 2\cdot 10^5$), consisting of lowercase English letters.

It is guaranteed that the sum of $|s|$ over all testcases does not exceed $2\cdot 10^5$.


-----Output-----

For each test case, print "YES" if $s$ is a perfectly balanced string, and "NO" otherwise.

You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as positive answer).


-----Examples-----

Input
5
aba
abb
abc
aaaaa
abcba
Output
YES
NO
YES
YES
NO


-----Note-----

Let $f_t(c)$ represent the frequency of character $c$ in string $t$.

For the first testcase we have

$t$

$f_t(a)$

$f_t(b)$

$a$

$1$

$0$

$ab$

$1$

$1$

$aba$

$2$

$1$

$b$

$0$

$1$

$ba$

$1$

$1$

It can be seen that for any substring $t$ of $s$, the difference between $f_t(a)$ and $f_t(b)$ is not more than $1$. Hence the string $s$ is perfectly balanced.

For the second testcase we have

$t$

$f_t(a)$

$f_t(b)$

$a$

$1$

$0$

$ab$

$1$

$1$

$abb$

$1$

$2$

$b$

$0$

$1$

$bb$

$0$

$2$

It can be seen that for the substring $t=bb$, the difference between $f_t(a)$ and $f_t(b)$ is $2$ which is greater than $1$. Hence the string $s$ is not perfectly balanced.

For the third testcase we have

$t$

$f_t(a)$

$f_t(b)$

$f_t(c)$

$a$

$1$

$0$

$0$

$ab$

$1$

$1$

$0$

$abc$

$1$

$1$

$1$

$b$

$0$

$1$

$0$

$bc$

$0$

$1$

$1$

$c$

$0$

$0$

$1$

It can be seen that for any substring $t$ of $s$ and any two characters $u,v\in\{a,b,c\}$, the difference between $f_t(u)$ and $f_t(v)$ is not more than $1$. Hence the string $s$ is perfectly balanced.

Source: codeforces | Difficulty: EASY
Tags: String algorithms

Complete search

Greedy algorithms


Solutions:
import sys

def solve():
	s = sys.stdin.readline().strip()
	w = set()
	for i in range(len(s)):
		c = s[i]
		if c in w:
			if c != s[0]:
				print('NO')
				return
			for j in range(i + 1, len(s)):
				if s[j] != s[j - i]:
					print('NO')
					return
			print('YES')
			return
		w.add(c)
	print('YES')

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


import sys
from sys import stdin
tt = int(stdin.readline())
ANS = []
for loop in range(tt):
	s = list(stdin.readline()[:-1])
	n = len(s)
	st = set()
	lp = None
	for i in range(n):
		if s[i] in st:
			lp = i
			break
		st.add(s[i])
	ans = 'YES'
	if lp == None:
		ANS.append(ans)
		continue
	for i in range(n):
		if s[i % lp] != s[i]:
			ans = 'NO'
	ANS.append(ans)
print('\n'.join(ANS))


import sys
input = sys.stdin.readline
n = int(input())
for _ in range(n):
	s = input()[:-1]
	a = len(s)
	b = len(set(s))
	if b == 1 or a == b:
		print('YES')
	else:
		for i in range(1, a):
			if s[i] in s[:i]:
				w = (s[:i] * a)[:a]
				if s == w:
					print('YES')
				else:
					print('NO')
				break


import sys
input = sys.stdin.readline

def solve():
	s = input().strip()
	n = len(s)
	cnt = {}
	for i in range(n):
		c = s[i]
		if c not in cnt:
			cnt[c] = 0
		cnt[c] += 1
	if max(cnt.values()) == 1 or len(cnt) == 1:
		return 'YES'
	else:
		cnt = {}
		for i in range(n):
			c = s[i]
			if c not in cnt:
				cnt[c] = 0
			cnt[c] += 1
			if cnt[c] == 2:
				pattern = s[:i]
				for j in range(i, n):
					if pattern[j % i] != s[j]:
						return 'NO'
				return 'YES'
for _ in range(int(input())):
	print(solve())


from collections import deque
import sys
input = sys.stdin.readline
for _ in range(int(input().rstrip())):
	s = input().rstrip()
	i = 0
	answer = 'YES'
	pattern = deque([])
	while i < len(s) and s[i] not in pattern:
		pattern.append(s[i])
		i += 1
	if i < len(s) and s[i] != pattern[0]:
		answer = 'NO'
	else:
		while i < len(s):
			if s[i] != pattern[0]:
				answer = 'NO'
				break
			else:
				pattern.rotate(-1)
			i += 1
	print(answer)


from sys import stdin
input = stdin.readline

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))
for _ in range(ii()):
	s = input().strip()
	n = len(s)
	cdn = 1
	ts = set(list(s))
	k = len(ts)
	for i in range(k):
		for j in range(i, n, k):
			if s[i] != s[j]:
				cdn = 0
	if cdn == 1:
		print('YES')
	else:
		print('NO')


tc = int(input())
for _ in range(tc):
	s = input()
	l = len(set(s))
	for i in range(l, len(s)):
		if s[i] != s[i - l]:
			print('NO')
			break
	else:
		print('YES')


t = int(input())
for caso in range(t):
	s = input()
	c = len(set(s))
	for i in range(c, len(s)):
		if s[i] != s[i - c]:
			print('NO')
			break
	else:
		print('YES')


def solve(s):
	n = len(s)
	k = len(set(s))
	for i in range(k, n):
		if s[i] != s[i - k]:
			return 'NO'
	return 'YES'
t = int(input())
for _ in range(t):
	s = input()
	print(solve(s))


for _ in range(int(input())):
	s = input()
	t = len(set(s))
	ans = True
	for i in range(len(s) - t):
		if s[i] == s[i + t]:
			continue
		else:
			ans = False
	print('YES' if ans else 'NO')


for _ in range(int(input())):
	s = input()
	k = len(set(s))
	for i in range(k, len(s)):
		if s[i] != s[i - k]:
			print('NO')
			break
	else:
		print('YES')


import math
for i in range(int(input())):
	s = input()
	a = set(s)
	b = len(a)
	for j in range(b, len(s)):
		if s[j] != s[j - b]:
			print('NO')
			break
	else:
		print('YES')


def solve(s):
	st = set(s)
	a = len(st)
	f = 1
	for i in range(len(s)):
		if s[i] != s[i % a]:
			f = 0
	if not f:
		return 'NO'
	else:
		return 'YES'
for i in range(int(input())):
	s = input()
	print(solve(s))


def main():
	for _ in range(int(input())):
		string = input()
		n = len(string)
		mp = {}
		flag = True
		for i in string:
			mp[i] = mp.get(i, 0) + 1
		count = len(mp)
		for i in range(0, n - count):
			if string[i] != string[i + count]:
				flag = False
		if flag:
			print('YES')
		else:
			print('NO')
main()


for _ in range(int(input())):
	S = input()
	L = []
	for i in S:
		if i in L:
			break
		else:
			L.append(i)
	N = len(L)
	i = 0
	for c in S:
		if c != L[i]:
			print('NO')
			break
		else:
			i += 1
			if i == N:
				i = 0
	else:
		print('YES')


t = int(input())
while t:
	s = input()
	st = set()
	flag = True
	k = 0
	for i in s:
		if i not in st:
			st.add(i)
			k += 1
		else:
			break
	for i in range(k, len(s)):
		if s[i] != s[i - k]:
			flag = False
	if flag:
		print('YES')
	else:
		print('NO')
	t -= 1


t = int(input())
for i in range(t):
	vis = set()
	dis = 0
	s = input()
	n = len(s)
	is_balanced = True
	for c in s:
		if c not in vis:
			dis += 1
			vis.add(c)
	for i in range(dis, n):
		if s[i] != s[i - dis]:
			is_balanced = False
	if is_balanced:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	triggered = False
	a = input()
	lst = list(a)
	n = len(set(a))
	for k in range(len(lst)):
		if n + k >= len(lst):
			break
		elif lst[k] != lst[k + n]:
			triggered = True
			break
	if triggered == True:
		print('NO')
	if triggered == False:
		print('YES')


t = int(input())
for i in range(t):
	s = input()
	m = set(s)
	k = len(m)
	flag = True
	for i in range(len(s)):
		if i + k < len(s):
			if s[i] != s[i + k]:
				flag = False
	if flag == False:
		print('NO')
	else:
		print('YES')


def main():
	t = int(input())
	for k in range(t):
		s = input()
		(freq, ans, pos, count) = ({}, True, len(s), 0)
		for i in range(len(s)):
			if freq.get(s[i]) is None:
				freq[s[i]] = 1
			else:
				freq[s[i]] += 1
		distinct_char = len(freq)
		for i in range(distinct_char, len(s)):
			if s[i] != s[count]:
				ans = False
				break
			count += 1
		if len(freq) == 1:
			ans = True
		if ans:
			print('YES')
		else:
			print('NO')
main()


for _ in range(int(input())):
	s = input()
	n = len(s)
	se = set(list(s))
	if len(se) == 1 or len(se) == n:
		print('YES')
	else:
		f = True
		for i in range(1, n):
			if s[i - 1] == s[i]:
				print('NO')
				f = False
				break
		if f:
			nse = len(se)
			r = s[:nse]
			q = n // nse
			rem = n % nse
			if r * q + r[:rem] == s:
				print('YES')
			else:
				print('NO')


t = int(input())
for _ in range(t):
	s = input()
	l = len(s)
	uniq = len(set(s))
	if uniq == 1 or uniq == l:
		print('YES')
	elif len(s[:uniq]) != uniq:
		print('NO')
	else:
		flag = 'YES'
		for i in range(l - uniq):
			if s[i] == s[i + uniq]:
				continue
			else:
				flag = 'NO'
				break
		print(flag)


def w(c):
	return ord(c) - 97
for _ in range(int(input())):
	s = input()
	f = True
	m = [False] * 26
	p = 0
	for i in range(len(s)):
		if m[w(s[i])]:
			if p:
				if s[i] != s[i - p]:
					f = False
					break
			elif s[i] == s[0]:
				p = i
			else:
				f = False
				break
		else:
			if p:
				f = False
				break
			m[w(s[i])] = True
	print('YES' if f else 'NO')


t = int(input(''))

def soltion(s):
	d = {}
	n = len(s)
	i = 0
	while i < n:
		if s[i] not in d:
			d[s[i]] = 1
			i = i + 1
		else:
			break
	ok = True
	for j in range(i, n):
		if s[j] != s[j - i]:
			ok = False
	if ok:
		return 'YES'
	else:
		return 'NO'
for i in range(t):
	s = input('')
	print(soltion(s))


for _ in range(int(input())):
	s = str(input())
	arr = []
	ans = []
	for i in s:
		if i not in arr:
			arr.append(i)
	n = len(arr)
	for i in range(len(s) - n):
		if s[i] != s[i + n]:
			ans.append('NO')
		else:
			ans.append('YES')
	x = 'NO'
	if x in ans:
		print('NO')
	else:
		print('YES')


t = int(input())
while t > 0:
	s = input()
	n = len(s)
	mp = dict()
	idx = n
	flag = 1
	for i in range(n):
		if s[i] in mp:
			mp[s[i]] += 1
		else:
			mp[s[i]] = 1
		if mp[s[i]] > 1:
			idx = i
			break
	for i in range(i, n):
		if s[i] != s[i % idx]:
			flag = 0
	if flag:
		print('YES')
	else:
		print('NO')
	t -= 1


def solution(content: str):
	char_dict = dict()
	for char in content:
		char_dict[char] = char_dict.get(char, 0) + 1
	n = len(char_dict)
	if n == 1:
		print('YES')
		return
	char_list = list(content[:n])
	if len(set(char_list)) < n:
		print('NO')
		return
	for (i, data) in enumerate(content):
		if data != char_list[i % n]:
			print('NO')
			return
	print('YES')
	return
t = int(input())
for i in range(t):
	content = input()
	solution(content)


t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	if n == 1:
		print('YES')
		continue
	cur = 0
	l = []
	l.append(s[0])
	ans = True
	rep = False
	for i in range(1, n):
		if not rep:
			if s[i] in l:
				rep = True
			else:
				l.append(s[i])
		if rep:
			if s[i] != s[cur]:
				ans = False
				break
			else:
				cur += 1
	if ans:
		print('YES')
	else:
		print('NO')


n = int(input())
for i in range(n):
	str1 = input()
	set_char = set(str1)
	req = len(set_char)
	prev = dict()
	truth = True
	ind = 0
	for i1 in str1:
		if i1 in prev and ind - prev[i1] != req:
			truth = False
			break
		prev[i1] = ind
		ind += 1
	print(truth and 'YES' or 'NO')


def get_ans():
	s = input()
	st = set()
	for c in s:
		st.add(c)
	cnt = len(st)
	mp = {}
	for i in range(len(s)):
		c = s[i]
		if c in mp and i - mp[c] + 1 <= cnt:
			print('NO')
			return
		mp[c] = i
	print('YES')
t = int(input())
for i in range(t):
	get_ans()


for j in range(0, int(input())):
	s = input()
	s1 = set(s)
	n = len(s1)
	if s.count(s[0]) == len(s):
		print('YES')
	else:
		ans = 'YES'
		for i in range(0, len(s) - 1):
			if s[i] == s[i + 1]:
				ans = 'NO'
				break
			if i + n < len(s):
				if s[i] != s[i + n]:
					ans = 'NO'
					break
		print(ans)


from math import ceil

def main():
	s = input()
	l = len(s)
	if len(set(s)) == 1:
		return 'YES'
	if len(set(s)) == l:
		return 'YES'
	f = -1
	for i in range(1, l):
		if s[i] == s[0]:
			f = i
			break
	if f == -1:
		return 'NO'
	if len(set(s[:f])) != f:
		return 'NO'
	atom = s[:f]
	times = ceil(l / len(atom))
	big = atom * times
	if big[:l] != s:
		return 'NO'
	return 'YES'
	i = 1
	left = 0
	right = f
	while right < l:
		if len(set(s[left:right])) != f:
			return 'NO'
		left += f
		right += f
	if len(set(s[left:])) != len(s[left:]):
		return 'NO'
	return 'YES'
for _ in range(int(input())):
	print(main())


t = int(input())
for _ in range(t):
	s = input()
	sSet = set()
	for i in range(len(s)):
		sSet.add(s[i])
	ok = 1
	for i in range(len(s)):
		if s[i] != s[i % len(sSet)]:
			ok = 0
	if ok:
		print('YES')
	else:
		print('NO')


from collections import Counter, deque
from collections import OrderedDict
import math
from random import randint
from bisect import bisect, bisect_left
import sys
import re
MOD = 10 ** 9 + 7
MAX = -sys.maxsize
MIN = sys.maxsize

class get:

	def int():
		return list(map(int, input().split()))

	def str():
		return input().split()

	def float():
		return list(map(float, input().split()))

	def map():
		return map(int, input().split())

def sqrt(x):
	return int(math.sqrt(x)) + 1

def gcd(*args):
	result = args[0]
	for item in args:
		result = math.gcd(result, item)
	return result

def LCM(a, b):
	return a * b // math.gcd(a, b)

def isPrime(n):
	if n == 1:
		return False
	for i in range(2, sqrt(n)):
		if n % i == 0:
			return False
	return True

def solve():
	s = input()
	x = set()
	j = 0
	for i in range(len(s)):
		if s[i] in x:
			j = i
			break
		x.add(s[i])
	for i in range(0, len(s) - j):
		if s[i] != s[i + j]:
			print('NO')
			return
	print('YES')
t = int(input())
for tt in range(t):
	solve()


for _ in range(int(input())):
	co = 'YES'
	s = input()
	sk = s[0]
	t = 0
	n = len(s)
	for i in range(1, n):
		if s[i] not in sk:
			sk += s[i]
		else:
			t = i
			break
	q = len(sk)
	for i in range(t, n, q):
		if s[i:i + q] == sk:
			continue
		elif s[i:i + q] == sk[:n - i]:
			continue
		else:
			co = 'NO'
			break
	print(co)


t = int(input())
while t > 0:
	s = input()
	n = len(s)
	l = set()
	l.add(s[0])
	if n < 2:
		print('YES')
	else:
		increasing = ord(s[1]) - ord(s[0])
		if increasing == 0:
			for i in range(n):
				if s[i] != s[0]:
					print('NO')
					break
			else:
				print('YES')
		else:
			for i in range(1, n):
				if s[i] in l:
					if s[i] == s[0]:
						for j in range(i, n):
							if s[j] != s[j % i]:
								print('NO')
								break
						else:
							print('YES')
						break
					else:
						print('NO')
						break
				else:
					l.add(s[i])
			else:
				print('YES')
	t = t - 1


n = int(input())
for i in range(0, n):
	s = input()
	ls = list(s)
	n = len(set(s))
	flag = 0
	for i in range(len(ls)):
		if i + n >= len(ls):
			break
		elif ls[i] != ls[i + n]:
			flag = 1
			break
	if flag:
		print('NO')
	else:
		print('YES')


from collections import defaultdict
t = int(input())
while t > 0:
	a = str(input())
	prev = defaultdict()
	for ch in a:
		prev[ch] = -1
	diff = len(prev)
	if len(prev) == 1 or len(prev) == len(a):
		print('YES')
		t -= 1
		continue
	f = 0
	for i in range(len(a)):
		if prev[a[i]] != -1:
			if i - prev[a[i]] == diff:
				prev[a[i]] = i
				f = 1
			else:
				f = 0
				print('NO')
				break
		else:
			prev[a[i]] = i
	if f == 1:
		print('YES')
	t -= 1


for _ in range(int(input())):
	l = input()
	d = {}
	x = 0
	for i in range(len(l)):
		if l[i] not in d:
			d[l[i]] = i
			x = x + 1
	d2 = {}
	for i in range(len(l)):
		if l[i] not in d2:
			d2[l[i]] = i
		elif i - d2[l[i]] >= x:
			d2[l[i]] = i
		else:
			print('NO')
			break
	else:
		print('YES')


for _ in range(int(input())):
	s = input()
	hsh = {}
	for c in s:
		if c not in hsh:
			hsh[c] = -1
	(n, h) = (len(s), len(hsh))
	for i in range(h):
		if hsh[s[i]] > -1:
			print('NO')
			break
		hsh[s[i]] = i
	else:
		for i in range(h, n):
			if hsh[s[i]] != i % h:
				print('NO')
				break
		else:
			print('YES')


for _ in range(int(input())):
	s = input()
	c = len(set(s))
	ans = True
	for i in range(c):
		if len(set(s[i::c])) != 1:
			ans = False
			break
	if ans:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = str(input())
	sz = len(set(list(s)))
	isPerfect = True
	lind = {}
	for i in range(len(s)):
		if s[i] not in lind:
			lind[s[i]] = i
		else:
			if i - lind[s[i]] < sz:
				isPerfect = False
				break
			lind[s[i]] = i
	if isPerfect:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	k = len(set(s))
	ans = True
	sub = []
	for x in s:
		if len(sub) == k:
			sub.pop(0)
		if x in sub:
			ans = False
		sub += (x,)
	print('YES' if ans else 'NO')


for _ in range(int(input())):
	s = input()
	n = len(set(s))
	print('YES' if all((len(set(s[i::n])) == 1 for i in range(n))) else 'NO')


t = eval(input())
for i in range(t):
	s = input()
	xh = ''
	for i in range(len(s)):
		if s[i] not in xh:
			xh += s[i]
		else:
			break
	ans = ''
	while len(s) - len(ans) >= len(xh):
		ans += xh
	ans += xh[:len(s) - len(ans)]
	if ans == s:
		print('YES')
	else:
		print('NO')


def verdict(s):
	_len = len(set(s))
	for i in range(len(s) - _len + 1):
		if len(set(s[i:i + _len])) != _len:
			return 'NO'
	else:
		return 'YES'
t = int(input())
for _ in range(t):
	s = input()
	print(verdict(s))


import sys
import string
from decimal import Decimal
from math import log, ceil

def inp():
	return int(input())

def inplist():
	return list(map(int, input().split()))

def inpstrlist():
	s = input()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	unique = sorted(list(set(s)))
	ln = len(unique)
	if ln == 1:
		print('YES')
		continue
	x = s[:ln]
	temp = x * ceil(n / ln)
	temp = temp[:n]
	print('YES' if temp == s else 'NO')


def ss(s):
	s = list(s)
	n = len(set(s))
	t = 0
	i = 0
	j = 0
	d = {}
	while i < len(s):
		if s[i] in d and d[s[i]] > 0:
			d[s[i]] += 1
			while j < i and d[s[i]] > 1:
				d[s[j]] -= 1
				if d[s[j]] == 0:
					t -= 1
				j += 1
			if n - t > 0:
				return 'NO'
			i += 1
		else:
			d[s[i]] = 1
			t += 1
			i += 1
	return 'YES'
for _ in range(int(input())):
	s = str(input())
	print(ss(s))


from collections import Counter

def value(string):
	counter = Counter(string)
	for i in counter:
		if counter[i] >= 2:
			temp = string.split(i)
			temp = temp[1:-1]
			temp = [len(set(item)) for item in temp]
			if min(temp) < len(counter) - 1:
				return 'NO'
	return 'YES'

def main():
	n = int(input())
	data = []
	for i in range(n):
		string = input()
		data.append(string)
	for string in data:
		print(value(string))
main()


for t in range(int(input())):
	s = input()
	s1 = s[0]
	n = len(s)
	d = {}
	a = s[0]
	c = n
	ch = True
	for i in s:
		d[i] = False
	d[a] = True
	for i in range(1, n):
		if s[i] != a:
			if d[s[i]]:
				ch = False
				break
			d[s[i]] = True
			s1 += s[i]
		else:
			c = i
			break
	x = n // c + 1
	s1 *= x
	if s != s1[:n]:
		ch = False
	if ch:
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	s = input()
	d = {}
	for i in s:
		if i in d.keys():
			d[i] += 1
		else:
			d[i] = 1
	l = list(d.keys())
	ok = 1
	for i in range(len(s)):
		if s[i] != s[i % len(l)]:
			ok = 0
			break
	if ok == 0:
		print('NO')
	else:
		print('YES')
	t -= 1


for _ in range(int(input())):
	s = input()
	n = len(s)
	a = set()
	b = ''
	for i in s:
		if i not in a:
			a.add(i)
			b += i
		else:
			break
	m = len(b)
	flag = True
	for i in range(n):
		if s[i] != b[i % m]:
			flag = False
			break
	if flag:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	s = input()
	alphabet = []
	for j in range(len(s)):
		if s[j] not in alphabet:
			alphabet.append(s[j])
	judge = 1
	str_a = s[0:len(alphabet)]
	for k in alphabet:
		if k not in str_a:
			judge = judge * 0
	balanced_str = str_a * (len(s) // len(alphabet)) + str_a[0:len(s) % len(alphabet)]
	if balanced_str != s:
		judge = judge * 0
	if judge == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	s = input()
	l = len(s)
	first = s[0]
	if l == 1 or s.count(first) == l:
		print('YES')
	elif s.count(first) > 1:
		j = 1
		strr = ''
		strr += s[0]
		num = [0] * 26
		num[ord(s[0]) - 97] += 1
		bad = 0
		while s[j] != s[0] and bad == 0:
			if num[ord(s[j]) - 97] == 0:
				num[ord(s[j]) - 97] += 1
				strr += s[j]
			else:
				bad = 1
			j += 1
		if bad == 1:
			print('NO')
		else:
			uno = l // len(strr)
			dos = l % len(strr)
			if s == strr * uno + strr[:dos]:
				print('YES')
			else:
				print('NO')
	else:
		num = [0] * 26
		num[ord(s[0]) - 97] += 1
		bad = 0
		j = 1
		while j < l and bad == 0:
			if num[ord(s[j]) - 97] == 0:
				num[ord(s[j]) - 97] += 1
			else:
				bad = 1
			j += 1
		if bad == 1:
			print('NO')
		else:
			print('YES')


for _ in range(int(input())):
	s = input()
	n = len(s)
	d = {}
	for i in s:
		if i not in d.keys():
			d[i] = 1
		else:
			d[i] += 1
	keys = list(d.keys())
	l = len(keys)
	new = ''
	for i in keys:
		new += i
	new = new * (n // l)
	for i in range(n % l):
		new += keys[i]
	if new == s:
		print('YES')
	else:
		print('NO')


t = int(input())

def q(l):
	lis = []
	i = 0
	n = 0
	for x in l:
		n += 1
		if x not in lis:
			lis.append(x)
			i += 1
	for j in range(i):
		for k in range(j, n, i):
			if l[k] != l[j]:
				return 'NO'
	return 'YES'
for i in range(t):
	a = input()
	l = list(a)
	print(q(l))


from string import ascii_lowercase
for i in range(int(input())):
	s = input()
	tmpl = ''
	n = -1
	check = [False] * 26
	for i in range(len(s)):
		if check[ord(s[i]) - ord('a')]:
			break
		check[ord(s[i]) - ord('a')] = True
		n = i + 1
	for i in range(len(s)):
		if s[i] != s[i % n]:
			print('NO')
			break
	else:
		print('YES')


import math
for _ in range(int(input())):
	s = input()
	data = {}
	for i in s:
		if i not in data:
			data[i] = 1
		else:
			data[i] += 1
	n = len(s)
	k = len(data)
	data2 = {}
	new = ''
	counter = 0
	for i in s:
		new += i
		if i not in data2:
			data2[i] = 1
			counter += 1
		else:
			data2[i] += 1
		if counter == k:
			break
	n2 = len(new)
	start = 0
	end = n2
	if n2 != k:
		print('NO')
		continue
	while end < n:
		start += n2
		end += n2
		if end > n:
			end = n
		if s[start:end] != new[:end - start]:
			print('NO')
			break
	else:
		print('YES')


for _ in range(int(input())):
	s = input()
	l = len(set(s))
	if l == 1:
		print('YES')
	else:
		f = 1
		for i in range(0, len(s) - l + 1):
			if len(set(s[i:i + l])) != l:
				f = 0
				break
		if f:
			print('YES')
		else:
			print('NO')


t = int(input())
for _ in range(0, t):
	s = input()
	list1 = []
	for i in range(0, len(s)):
		if s[i] not in list1:
			list1.append(s[i])
	flag = 0
	if len(list1) == 1:
		flag = 0
	else:
		len1 = len(list1)
		reps = 0
		j = 0
		flag = 0
		for i in range(0, len(s)):
			if s[i] == list1[j]:
				reps += 1
				j += 1
			else:
				flag = 1
				break
			if reps == len(list1):
				reps = 0
				j = 0
	if flag == 0:
		print('YES')
	else:
		print('NO')


loopcount = int(input())
for loop in range(loopcount):
	s = input()
	output = 'YES'
	dict = {}
	for i in range(len(s)):
		if s[i] in dict.keys():
			dict[s[i]].append(i)
		else:
			dict[s[i]] = [i]
	chars = len(dict.keys())
	for i in dict.keys():
		for j in range(len(dict[i]) - 1):
			diff = dict[i][j + 1] - dict[i][j]
			if chars > diff:
				output = 'NO'
				break
		if output == 'NO':
			break
	print(output)


T = int(input())
while T:
	s = input()
	numUnique = len(set(s))
	ans = 'YES'
	for i in range(numUnique, len(s) + 1):
		if len(set(s[i - numUnique:i])) != numUnique:
			ans = 'NO'
	print(ans)
	T -= 1


t = int(input())
while t > 0:
	s = input()
	n = len(s)
	d = [0 for i in range(26)]
	ind = n
	for i in range(n):
		r = ord(s[i]) - ord('a')
		d[r] += 1
		if d[r] > 1:
			ind = i
			break
	fl = 0
	for i in range(ind, n):
		if s[i] != s[i - ind]:
			fl = -1
			break
	if fl == -1:
		print('NO')
	else:
		print('YES')
	t -= 1


for _ in range(int(input())):
	s = input()
	s1 = set(s)
	if len(s1) == 1:
		print('YES')
		continue
	s2 = set()
	pat = ''
	x = 0
	for i in range(len(s)):
		if s[i] not in s2:
			pat += s[i]
			s2.add(s[i])
		else:
			x = i
			break
	if len(s2) != len(s1):
		print('NO')
		continue
	j = 0
	f = 1
	for i in range(x, len(s)):
		if pat[j % len(pat)] != s[i]:
			print('NO')
			f = 0
			break
		j += 1
	if f:
		print('YES')


t = int(input())
while t > 0:
	t -= 1
	s = str(input())
	var = set(s)
	ans = 'YES'
	for i in range(len(s) - len(var) + 1):
		if len(set(s[i:i + len(var)])) != len(var):
			ans = 'NO'
			break
	print(ans)


tc = int(input())
for case in range(tc):
	s = input()
	chars = set(s)
	if len(chars) == 1:
		print('YES')
		continue
	if any((len(set(s[i:i + len(chars)])) < len(chars) for i in range(len(s) - len(chars) + 1))):
		print('NO')
	else:
		print('YES')


n = int(input())
for _ in range(n):
	s = input()
	ans = True
	d = {}
	for i in range(len(s)):
		if s[i] not in d:
			d[s[i]] = []
		d[s[i]].append(i)
	diff = len(d)
	flag = True
	for i in d:
		temp = d[i]
		for i in range(len(temp) - 1):
			if temp[i + 1] - temp[i] != diff:
				flag = False
				break
	if flag:
		print('YES')
	else:
		print('NO')


n = int(input())
for _ in range(n):
	s = input()
	m = [False] * 26
	word = []
	for c in s:
		if m[ord(c) - ord('a')]:
			break
		word.append(c)
		m[ord(c) - ord('a')] = True
	word = ''.join(word)
	for i in range(0, len(s), len(word)):
		if not word.startswith(s[i:i + len(word)]):
			print('NO')
			break
	else:
		print('YES')