Назовём строку \(s\) идеально сбалансированной, если для всех возможных троек \((t,u,v)\) таких, что \(t\) является непустой подстрокой \(s\), а \(u\) и \(v\) являются символами, присутствующими в \(s\), разница в количествах вхождений \(u\) и \(v\) в \(t\) отличается не более, чем на \(1\).
Например, строки «aba» и «abc» являются идеально сбалансированными, а «abb» нет, потому что для тройки («bb»,'a','b') условие не выполняется.
Вам дана строка \(s\), состоящая только из строчных латинских букв. Ваша задача состоит в том, чтобы определить, является ли \(s\) идеально сбалансированной или нет.
Строка \(b\) называется подстрокой строки \(a\), если \(b\) может быть получена удалением нескольких (возможно \(0\)) символов из начала и нескольких (возможно \(0\)) символов из конца \(a\).
Выходные данные
Для каждого набора входных данных выведите «YES», если \(s\) является идеально сбалансированной, и «NO» иначе.
Вы можете выводить каждую букву в любом регистре (например, «YES», «Yes», «yes», «yEs» будут распознаны как положительный ответ).
Примечание
Пусть \(f_t(c)\) обозначает количество вхождений символа \(c\) в строку \(t\).
Для первого набора входных данных получается:
| \(t\) | \(f_t(a)\) | \(f_t(b)\) |
| \(a\) | \(1\) | \(0\) |
| \(ab\) | \(1\) | \(1\) |
| \(aba\) | \(2\) | \(1\) |
| \(b\) | \(0\) | \(1\) |
| \(ba\) | \(1\) | \(1\) |
Можно увидеть, что для любой подстроки
\(t\) в
\(s\), разница между
\(f_t(a)\) и
\(f_t(b)\) не превышает
\(1\). Значит, строка
\(s\) идеально сбалансирована.
Для второго набора входных данных получается:
| \(t\) | \(f_t(a)\) | \(f_t(b)\) |
| \(a\) | \(1\) | \(0\) |
| \(ab\) | \(1\) | \(1\) |
| \(abb\) | \(1\) | \(2\) |
| \(b\) | \(0\) | \(1\) |
| \(bb\) | \(0\) | \(2\) |
Можно увидеть, что для подстроки
\(t=bb\), разница в количествах вхождений
\(f_t(a)\) и
\(f_t(b)\) равна
\(2\), что больше
\(1\). Значит, строка
\(s\) не идеально сбалансирована.
Для третьего набора входных данных получается:
| \(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\) |
Можно увидеть, что для любой подстроки \(t\) в \(s\) и любых двух символов \(u,v\in\{a,b,c\}\), разница между \(f_t(u)\) и \(f_t(v)\) не превышает \(1\). Значит, строка \(s\) идеально сбалансирована.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
aba
abb
abc
aaaaa
abcba
|
YES
NO
YES
YES
NO
|