Удалить неверные скобки

Question

Удалите недопустимые скобки, используя Python в O (n) сложности времени и O (1) пространства.У меня есть несколько подходов, которые займут O (n log n) и O (n ^ 2) время, а также O (n) как пространство, так и время.Но я ищу тот, который минимальное время.Я попытался выполнить поиск в Интернете, но не смог найти какой-либо подход к решению.

Например:

input - {}{}{{}}}}}{{{{{}
output - {}{}{{}}{}

Существует также несколько других крайних случаев.

Answer 1

В данном примере уровни вложенности следующие:

 { } { } { { } } } } } { { { { { }
 1 0 1 0 1 2 1 0-1-2-3-2-1 0 1 2 1

Если вы отбрасываете отрицательные (на лету),

 { } { } { { } } { { { { { }
 1 0 1 0 1 2 1 0 1 2 3 4 5 4

Теперь повторите с правой стороны.

 { } { } { { } } { { { { { }
-2-3-2-3-4-3-2-3-4-3-2-1 0 1

и

 { } { } { { } } { }
 0 1 0 1 0 1 2 1 0 1