Дана скобочная последовательность из круглых скобок, скорее всего неправильная.
Можно ли сделать её правильной, заменив ровно одну скобку на противоположную
(( ↔ ))? Если можно — верните индекс этой скобки, иначе -1.
// FlipToBalance возвращает индекс скобки, замена которой делает s правильной, или -1.
func FlipToBalance(s string) int
Если подходящих индексов несколько, верните любой.
Примеры
"(()))(" → -1 (замена одной скобки не спасает)
"())" → -1 (нечётная длина)
"()))" → 2 ("()()"), также подходит 1 ("(())")
"((((" → -1
"(())((" → 5 ("(())()")
")(" → -1
"(())" → -1 (уже правильная: любая замена её сломает)
Ограничения
0 ≤ len(s) ≤ 10⁶, в строке только ( и ).- Ожидается O(n) по времени. Перебор «заменить каждую и проверить» — O(n²), не пройдёт.
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.