У Ashish есть строка \(s\) длины \(n\), содержащая только символы 'a', 'b' и 'c'.
Он хочет найти длину наименьшей подстроки, которая удовлетворяет следующим условиям:
- Длина подстроки не меньше чем \(2\)
- 'a' встречается строго больше раз в этой подстроке, чем 'b'
- 'a' встречается строго больше раз в этой подстроке, чем 'c'
Ashish занят планированием следующего раунда Codeforces. Помогите ему решить задачу.
Строка \(a\) является подстрокой строки \(b\), если \(a\) можно получить из \(b\), удалив несколько (возможно, ноль или все) символов из начала и несколько (возможно, ноль или все) символов из конца.
Выходные данные
Для каждого набора входных данных выведите длину наименьшей подстроки, удовлетворяющей заданным условиям, или выведите \(-1\), если такой подстроки нет.
Примечание
Рассмотрим первый набор входных данных. В подстроке «aa», 'a' встречается дважды, а 'b' и 'c' встречаются ноль раз. Поскольку 'a' встречается строго больше раз, чем 'b' и 'c', подстрока «aa» удовлетворяет условию, и ответ равен \(2\). Подстрока «a» также удовлетворяет этому условию, однако ее длина меньше \(2\).
Во втором наборе входных данных можно показать, что ни в одной из подстрок «cbabb» 'a' не встречается строго больше раз, чем 'b' и 'c'.
В третьем наборе входных данных, «cacabccc», длина наименьшей подстроки, удовлетворяющей условиям, равна \(3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2
aa
5
cbabb
8
cacabccc
|
2
-1
3
|