A Perfectly Balanced String? (Codeforces 1673B)
Tags: Greedy, strings

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).

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.

Sample Inputs:
5
aba
abb
abc
aaaaa
abcba

Sample Outputs:
YES
NO
YES
YES
NO

Solution (Python):
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()
if __name__ == '__main__':
    main()

Solution (Python):
import sys
import copy
import heapq
import bisect
import functools
from math import *
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import groupby
import itertools
from itertools import accumulate
from decimal import Decimal, ROUND_HALF_UP
readline = lambda : sys.stdin.readline().rstrip()

def solve():
    s = str(readline())
    n = len(s)
    st = set(s)
    k = len(st)
    for i in range(n):
        if s[i] != s[i % k]:
            print('NO')
            return
    print('YES')

def main():
    t = 1
    t = int(readline())
    for i in range(t):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
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