Read problem statements in [Hindi],[Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

One day, Saeed was teaching a string compression algorithm. This algorithm finds all maximal substrings which contains only one character repeated one or more times (a substring is maximal if it we cannot add one character to its left or right without breaking this property) and replaces each such substring by the string "cK", where $K$ is the length of the substring and $c$ is the only character it contains. For example, "aabaaa" is compressed to "a2b1a3".

Saeed wanted to check if the students understood the algorithm, so he wrote a string $S$ on the board and asked the students if the algorithm is effective on $S$, i.e. if the string created by compressing $S$ is strictly shorter than $S$. Help them answer this question.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains a single string $S$.

------  Output ------
For each test case, print a single line containing the string "YES" if the algorithm is effective on $S$ or "NO" if it is not.

------  Constraints ------
$1 ≤ T ≤ 100$
$1 ≤ |S| ≤ 10^{3}$
$S$ may consist of only lowercase English letters.

------  Subtasks ------
Subtask #1 (100 points): original constraints

----- Sample Input 1 ------ 
3

bbbbbbbbbbaa

c

aaaaaaaaaabcdefgh
----- Sample Output 1 ------ 
YES

NO

NO
----- explanation 1 ------ 
Example case 1:
- The compressed string of "bbbbbbbbbbaa" is "b10a2", which is shorter.
- The compressed string of "c" is "c1", which is not shorter than "c".
- The compressed string of "aaaaaaaaaabcdefgh" is "a10b1c1d1e1f1g1h1", which is not shorter than "aaaaaaaaaabcdefgh" (both strings have length $17$).

Source: codechef | Difficulty: EASY
Tags: Implementation

Complete search


Solutions:
t = int(input())
for i in range(t):
	s = input()
	final = ''
	prev = s[0]
	c = 1
	for i in range(1, len(s)):
		if s[i] == prev:
			c += 1
		else:
			final += prev + str(c)
			prev = s[i]
			c = 1
	final += prev + str(c)
	if len(final) < len(s):
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	s = input()
	c = 0
	r = ''
	st = s[0]
	for i in s:
		if st == i:
			c = c + 1
		else:
			r = r + i + str(c)
			st = i
			c = 1
	r = r + i + str(c)
	if len(r) < len(s):
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	t = t - 1
	s = input()
	g = s[0]
	r = ''
	h = 0
	j = 0
	k = 0
	for i in s:
		if g == i:
			h = h + 1
		else:
			r = r + g + str(h)
			g = i
			h = 1
	r = r + g + str(h)
	if len(r) < len(s):
		print('YES')
	else:
		print('NO')


t = int(input())
for tc in range(t):
	s = input()
	d = 1
	c = ''
	for j in range(len(s) - 1):
		if s[j] == s[j + 1]:
			d += 1
		else:
			c += s[j] + str(d)
			d = 1
	c += s[-1] + str(d)
	if len(c) >= len(s):
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	S = input()
	res = ''
	c = 1
	for i in range(len(S) - 1):
		if S[i] == S[i + 1]:
			c += 1
		else:
			res += S[i] + str(c)
			c = 1
	res += S[-1] + str(c)
	print('YES' if len(res) < len(S) else 'NO')


t = int(input())
for i in range(t):
	s = input()
	com_s = ''
	count = 0
	cur_c = ''
	for i in range(len(s)):
		if s[i] != cur_c:
			if count:
				com_s += cur_c + str(count)
			count = 1
			cur_c = s[i]
		else:
			count += 1
	com_s += cur_c + str(count)
	if len(com_s) < len(s):
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	s = input()
	k = 1
	l = 0
	p = len(s) - 1
	for j in range(p):
		if s[j] == s[j + 1]:
			k = k + 1
		else:
			l = l + len(str(k)) + 1
	if p > l:
		print('YES')
	else:
		print('NO')


t = int(input())
while t:
	t -= 1
	s = input()
	s1 = ''
	i = 0
	while i < len(s):
		j = i
		while j < len(s) and s[j] == s[i]:
			j += 1
		s1 += str(s[i]) + str(j - i)
		i = j
	if len(s) > len(s1):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	S = list(input())
	S.append('0')
	c = 0
	cc = 1
	x = S[0]
	for i in S[1:]:
		if i == x:
			cc += 1
		else:
			c += len(str(cc)) + 1
			cc = 1
			x = i
	if c < len(S) - 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	st = input()
	s = ''
	i = 0
	while i < len(st):
		j = i
		while j < len(st) and st[j] == st[i]:
			j += 1
		s += st[i] + str(j - i)
		i = j
	print('YES' if len(st) > len(s) else 'NO')


t = int(input())
for i in range(t):
	s = input()
	l = s[0]
	cou = 1
	out = ''
	for i in range(1, len(s)):
		if s[i] == l:
			cou += 1
		else:
			out += l + str(cou)
			l = s[i]
			cou = 1
	out += l + str(cou)
	if len(out) < len(s):
		print('YES')
	else:
		print('NO')


t = int(input())
for ni in range(t):
	s = input()
	count = 1
	s1 = ''
	x = s[0]
	s = s + ' '
	n = len(s)
	for i in range(1, n):
		if s[i] == x:
			count = count + 1
		else:
			s1 = s1 + x + str(count)
			count = 1
			x = s[i]
	if len(s1) < n - 1:
		print('YES')
	else:
		print('NO')


T = int(input())
for i in range(T):
	S = input()
	l = len(S)
	new = ''
	prev = 'none'
	for i in range(l):
		if prev != S[i]:
			new = new + S[i]
			subnew = ''
			prev = S[i]
			subnew = subnew + prev
			for j in range(i + 1, l):
				if S[j] == S[i]:
					subnew = subnew + S[j]
				else:
					break
			m = str(len(subnew))
			new = new + m
		else:
			pass
	z = len(new)
	if z < l:
		print('YES')
	else:
		print('NO')


n = int(input())
for i in range(n):
	list1 = []
	p = input()
	list2 = []
	for j in p:
		if j not in list2:
			list2.append(j)
	t = p[:]
	q = 0
	r = 0
	while r < len(p):
		new = ''
		while r != len(p) and p[q] == p[r]:
			new += p[r]
			r += 1
		list1.append(new)
		q = r
	leo = ''
	for j in list1:
		leo = leo + j[0] + str(len(j))
	if len(leo) < len(p):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	ans = ''
	prev = None
	num = 0
	for i in s:
		if prev != i:
			if prev != None:
				ans += f'{prev}{num}'
			prev = i
			num = 1
		else:
			num += 1
	ans += f'{prev}{num}'
	if len(s) > len(ans):
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	s = input()
	s1 = ''
	c = 1
	if len(s) < 2:
		print('NO')
		continue
	for i in range(len(s) - 1):
		if i + 1 == len(s) - 1:
			if s[i] == s[i + 1]:
				s1 += s[i] + str(c + 1)
			else:
				s1 += s[i] + str(c)
		elif s[i] == s[i + 1]:
			c += 1
		else:
			s1 += s[i] + str(c)
			c = 1
	if s[-1] != s[-2]:
		s1 += s[-1] + '1'
	if len(s1) < len(s):
		print('YES')
	else:
		print('NO')


T = int(input())
for i in range(T):
	s = input()
	out = ''
	for j in range(len(s)):
		if j > 0:
			if s[j] == s[j - 1]:
				continue
			m = s.count(s[j])
			out += s[j] + str(m)
			m = 0
		else:
			m = s.count(s[j])
			out += s[j] + str(m)
			m = 0
	if len(out) < len(s):
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	s = input()
	l = len(s)
	u = ''
	a = ' '
	for j in range(l):
		if a != s[j]:
			c = s.count(s[j])
			u = u + s[j] + str(c)
			a = s[j]
	if len(u) >= l:
		print('NO')
	else:
		print('YES')


t = int(input())
while t:
	s = input()
	n = len(s)
	c = 0
	s = s + ')'
	r = ''
	for i in range(n):
		if s[i] == s[i + 1]:
			c += 1
		else:
			r += s[i] + str(c + 1)
			c = 0
	print('YES') if len(r) < n else print('NO')
	t -= 1


t = int(input())
for _ in range(t):
	s = input()
	x = list(s)
	lis = []
	for i in range(len(s) - 1):
		if s[i] != s[i + 1]:
			lis.append(i)
	for i in range(len(lis)):
		x.insert(lis[i] + 1 + i, '0')
	y = ''.join(x)
	z = y.split('0')
	lis1 = []
	for i in range(len(z)):
		lis1.append(str(z[i][0]))
		lis1.append(str(len(z[i])))
	f = ''.join(lis1)
	if len(f) < len(s):
		print('YES')
	else:
		print('NO')


turns = int(input())
for turn in range(turns):
	st = input()
	temp = st[0]
	fs = ''
	c = 0
	for i in range(0, len(st)):
		if temp == st[i]:
			c += 1
			temp = st[i]
		else:
			fs += temp
			fs += str(c)
			c = 1
			temp = st[i]
	fs += str(st[len(st) - 1])
	fs += str(c)
	if len(fs) < len(st):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	if len(s) < 3:
		print('NO')
	else:
		sh = s[0]
		run = 1
		for i in range(1, len(s)):
			if s[i] == sh[-1]:
				run += 1
			else:
				sh += str(run) + s[i]
				run = 1
		sh += str(run)
		if len(sh) < len(s):
			print('YES')
		else:
			print('NO')


for tc in range(int(input())):
	s = input().strip()
	char = s[0]
	newstr = ''
	cnt = 1
	for i in range(1, len(s)):
		newchar = s[i]
		if newchar == char:
			cnt += 1
		else:
			newstr = newstr + (char + str(cnt))
			cnt = 1
			char = newchar
	newstr = newstr + (char + str(cnt))
	if len(newstr) < len(s):
		print('YES')
	else:
		print('NO')


n = int(input())
for i in range(n):
	lst = str()
	s = input()
	for i in range(0, len(s)):
		if i > 0:
			if s[i] == s[i - 1]:
				continue
			c = s.count(s[i])
			lst += str(s[i])
			lst += str(c)
			c = 0
		else:
			c = s.count(s[i])
			lst += str(s[i])
			lst += str(c)
			c = 0
	if len(lst) < len(s):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = str(input())
	n = len(s)
	s1 = ''
	c = 1
	for i in range(n):
		if i < n - 1:
			if s[i] == s[i + 1]:
				c += 1
			if s[i] != s[i + 1]:
				s1 += s[i] + str(c)
				c = 1
		else:
			s1 += s[i] + str(c)
	if len(s1) < n:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	newS = ''
	VisitedChar = []
	for i in range(len(s)):
		ct = 0
		char = s[i]
		for j in range(i, len(s)):
			if s[j] == char:
				ct += 1
			else:
				break
		if char not in VisitedChar:
			VisitedChar = []
			newS = newS + (char + str(ct))
			VisitedChar.append(char)
	print('YES') if len(newS) < len(s) else print('NO')


for _ in range(int(input())):
	a = input()
	b = len(a)
	c = ''
	if b == 1:
		print('NO')
	else:
		count = 1
		for i in range(1, b):
			if a[i] == a[i - 1]:
				count += 1
			else:
				c += a[i - 1] + str(count)
				count = 1
		if a[-1] != a[-2]:
			c += a[-1] + '1'
		else:
			c += a[-1] + str(count)
		if len(c) >= len(a):
			print('NO')
		else:
			print('YES')


a = int(input())
for _ in range(a):
	b = input()
	c = ''
	eq = b[0]
	cnt = 1
	for i in range(1, len(b)):
		if eq == b[i]:
			cnt += 1
		else:
			c = c + eq + str(cnt)
			eq = b[i]
			cnt = 1
	c = c + eq + str(cnt)
	if len(c) < len(b):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	l = ''
	for i in range(len(s)):
		if i > 0:
			if s[i] == s[i - 1]:
				continue
			c = s.count(s[i])
			l += str(s[i]) + str(c)
		else:
			c = s.count(s[i])
			l += str(s[i]) + str(c)
	if len(l) < len(s):
		print('YES')
	else:
		print('NO')


t = int(input())
for j in range(t):
	s = input()
	i = 0
	res = ''
	while i < len(s):
		c = 1
		while i < len(s) - 1 and s[i] == s[i + 1]:
			i += 1
			c += 1
		res += str(s[i]) + str(c)
		i += 1
	if len(res) < len(s):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	count = 0
	s = input()
	leng = len(s)
	new = ''
	prev = s[0]
	for i in range(leng + 1):
		if i < leng:
			if s[i] == prev:
				count += 1
			else:
				new = new + prev + str(count)
				count = 1
				prev = s[i]
		elif i == leng:
			new = new + prev + str(count)
		else:
			pass
	if leng > len(new):
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	s = input()
	s = s + ')'
	prev = '!'
	ans = ''
	c = 1
	for i in range(0, len(s)):
		if s[i] != prev and i != 0:
			ans = ans + str(c) + s[i]
			prev = s[i]
			c = 1
		elif s[i] != prev and i == 0:
			ans = ans + s[i]
			prev = s[i]
			c = 1
		else:
			c = c + 1
	if len(ans[:-1]) < len(s[:-1]):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = str(input())
	news = ''
	i = 0
	n = 0
	while i < len(s):
		n = 1
		while i + n < len(s) and s[i] == s[i + n]:
			n = n + 1
		news = news + s[i] + str(n)
		i = i + n
	if len(news) < len(s):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	m = 1
	S = ''
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			m += 1
		else:
			S += s[i] + str(m)
	if len(S) < len(s) and len(s) > 1:
		print('YES')
	elif len(s) == 1:
		print('NO')
	else:
		print('NO')


for i in range(int(input())):
	s = input()
	string = ''
	count = 1
	string += s[0]
	for i in range(1, len(s)):
		if s[i - 1] == s[i]:
			count += 1
		else:
			string += str(count) + s[i]
			count = 1
	string += str(count)
	if len(string) >= len(s):
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	s = input()
	arr = []
	ans = 0
	countr = 0
	a = s[0]
	countr = countr + s.count(s[0])
	arr.append(countr)
	countr = 0
	for i in range(1, len(s)):
		countr = 0
		if a != s[i]:
			countr = s.count(s[i])
			a = s[i]
			arr.append(countr)
	for j in range(len(arr)):
		a = str(arr[j])
		ans = ans + len(a) + 1
	if ans >= len(s):
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	st = input()
	sum1 = 0
	j = 0
	count = 1
	while j < len(st) - 1:
		if st[j] == st[j + 1]:
			count += 2
		else:
			sum1 += len(str(count)) + 1
			count = 1
		j += 1
	sum1 += len(str(count)) + 1
	if sum1 < len(st):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	l = []
	i = 0
	cnt = 1
	res = ''
	while i < len(s):
		k = i + 1
		while k < len(s) and s[i] == s[k]:
			k = k + 1
		res = res + s[i] + str(k - i)
		i = k
	if len(s) > len(res):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	a = ''
	a += s[0]
	c = 1
	for i in range(1, len(s)):
		if s[i - 1] == s[i]:
			c += 1
		else:
			a += str(c) + s[i]
			c = 1
	a += str(c)
	if len(a) < len(s):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	a = input()
	cnt = 1
	res = ''
	if len(a) == 1:
		res += a + str(1)
	else:
		for n in range(1, len(a)):
			if a[n - 1] == a[n]:
				i = a[n]
				cnt += 1
				if n == len(a) - 1:
					res += i + str(cnt)
			else:
				res += i + str(cnt)
				cnt = 1
				i = a[n]
				if n == len(a) - 1:
					res += i + str(cnt)
	if len(res) < len(a):
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	s = input()
	s1 = ''
	c = 0
	for i in range(0, len(s)):
		if i > 0:
			if s[i] != s[i - 1]:
				s1 = s1 + s[i - 1] + str(c)
		c = c + 1
	if len(s1) >= len(s) or c == -1 or len(s) == 1:
		print('NO')
	else:
		print('YES')


for jj in range(int(input())):
	s = input()
	cs = ''
	last = s[0]
	c = 1
	for i in s[1:]:
		if i == last:
			c += 1
		else:
			cs = cs + last + str(c)
			last = i
			c = 1
	cs = cs + last + str(c)
	if len(cs) < len(s):
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	s = input()
	r = ''
	u = s[0]
	v = 1
	for i in s[1:]:
		if i == u:
			v += 1
		else:
			r = r + u + str(v)
			u = i
			v = 1
	r = r + u + str(v)
	if len(r) < len(s):
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	s1 = input()
	s2 = ''
	first = s1[0]
	c = 1
	for i in s1[1:]:
		if i == first:
			c += 1
		else:
			s2 = s2 + first + str(c)
			first = i
			c = 1
	s2 = s2 + first + str(c)
	if len(s2) < len(s1):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	n = len(s)
	s += '#'
	x = 0
	cnt = 1
	for i in range(n):
		if s[i + 1] != s[i]:
			x += len(str(cnt)) + 1
			cnt = 1
		else:
			cnt += 1
	if x < n:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input('')
	c = 1
	size = 0
	ss = set(s)
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			c += 1
		else:
			size += len(str(c)) + 1
			c = 1
	size += len(str(c)) + 1
	if size < len(s):
		print('YES')
	else:
		print('NO')


T = int(input())
for i in range(T):
	s = str(input())
	i = 0
	ans = ''
	while i < len(s):
		j = i + 1
		c = 1
		while j < len(s) and s[j] == s[i]:
			c += 1
			j = j + 1
		ans += s[i] + str(c)
		i = j
	if len(ans) < len(s):
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	s = input()
	(size, cou) = (0, 1)
	for char in range(len(s) - 1):
		if s[char] == s[char + 1]:
			cou += 1
		else:
			size += len(str(cou)) + 1
			cou = 1
	size += len(str(cou)) + 1
	if size >= len(s):
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	S = input().strip() + '0'
	x = S[0]
	freq = 0
	T = ''
	for c in S:
		if c == x and c != '0':
			freq += 1
		elif c != x and c != '0':
			T += x + str(freq)
			x = c
			freq = 1
		if c == '0':
			T += x + str(freq)
			break
	print('YES') if len(S) - 1 > len(T) else print('NO')


a = int(input())
for i in range(a):
	s = input()
	out = ''
	counter = 0
	for x in range(0, len(s)):
		if x > 0:
			if s[x] != s[x - 1]:
				out = out + s[x - 1] + str(counter)
		counter = counter + 1
	if len(out) >= len(s) or counter == -1 or len(s) == 1:
		print('NO')
	else:
		print('YES')


t = input()
for c in range(0, int(t)):
	s = input()
	out = ''
	counter = 0
	for x in range(0, len(s)):
		if x > 0:
			if s[x] != s[x - 1]:
				out = out + s[x - 1] + str(counter)
		counter = counter + 1
	if len(out) >= len(s) or counter == -1 or len(s) == 1:
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(0, t):
	s = str(input())
	n = len(s)
	count = 1
	p = ''
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			count += 1
		else:
			p = p + s[i] + str(count)
			count = 1
	if s[n - 1] == s[n - 2]:
		p += s[n - 1]
		p += str(count)
	else:
		p += s[n - 1]
		p += str(1)
	if len(p) < n:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	count = 1
	st = ''
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			count += 1
		else:
			st += s[i]
			st += str(count)
			count = 1
	if s[n - 1] == s[n - 2]:
		st += s[n - 1]
		st += str(count)
	else:
		st += s[n - 1]
		st += str(1)
	if len(st) < len(s):
		print('YES')
	else:
		print('NO')