Идея:

Одна из ключевых особенностей допустимых строк в круглых скобках заключается в том, что они полностью самодостаточны, а это означает, что хотя одна подстрока может полностью находиться внутри другой, у вас не может быть двух подстрок, которые лишь частично перекрываются.

Это означает, что мы можем использовать жадную временную сложность O(N) для этой проблемы без необходимости какого-либо поиска с возвратом. На самом деле, мы должны иметь возможность использовать очень стандартный строковый алгоритм допустимых круглых скобок на основе стека всего с тремя очень незначительными модификациями.

В стандартном алгоритме строки с допустимыми скобками мы перебираем строку (S) и помещаем индекс (i) любого '(' в наш стек. Всякий раз, когда мы находим ')', мы сопоставляем его с последней записью в стеке и удаляем указанную запись. Мы знаем, что строка недействительна, если мы находим ')', когда в стеке нет индексов '(', с которыми можно сопоставить это, а также если у нас останется '(' в стеке, когда мы дойдем до конца S.

Для этой задачи нам нужно будет добавить шаг, который обновляет наш ответ (ans), когда мы закрываем пару скобок. Так как мы сохранили индекс '(' в нашем стеке, мы можем легко найти разницу между ')' в i и последняя запись в стеке, которая должна быть длиной допустимой подстроки, которая только что была закрыта.

Но здесь мы сталкиваемся с проблемой, поскольку последовательные допустимые подстроки могут быть сгруппированы в более крупную допустимую подстроку (например, ‘()()’ = 4). Таким образом, вместо того, чтобы считать от последней записи стека, мы должны фактически считать от второй до последней записи, чтобы включить любые другие допустимые закрытые подстроки, поскольку самый последний '(', который все еще останется после того, как мы вытолкнем только что сопоставленную последнюю запись stack.

Это, конечно, подводит нас ко второму и третьему изменениям. Поскольку мы проверяем предпоследнюю запись стека, что происходит в случае '()()', когда вы закрываете вторую допустимую подстроку, но есть только одна Осталась запись стека?

Чтобы избежать этой проблемы, мы можем просто заключить всю строку в другой воображаемый набор круглых скобок, начав с stack = [-1], указывая, что существует воображаемый '(' непосредственно перед началом строки в точке i = 0.

Другая проблема заключается в том, что мы захотим продолжить, даже если строка до i станет недействительной из-за появления ')', когда стек является «пустым», или в этом случае у него остался только наш воображаемый индекс. В этом случае мы можем просто эффективно перезапустить наш стек, обновив наш воображаемый индекс '(' (stack[0] = i) и продолжить на.

Затем, как только мы достигнем конца S, мы можем просто вернуть ответ.

Реализация:

Есть лишь незначительные различия в коде для всех четырех языков.

Код JavaScript:

Наилучший результат для приведенного ниже кода — 76 мс / 39,9 МБ (лучше 99% / 78%).

var longestValidParentheses = function(S) {
     let stack = [-1], ans = 0
     for (let i = 0; i < S.length; i++)
          if (S[i] === '(') stack.push(i)
          else if (stack.length === 1) stack[0] = i
          else stack.pop(), ans = Math.max(ans, i - stack[stack.length-1])
     return ans
};

Код Python:

Наилучший результат для приведенного ниже кода — 40 мс / 14,6 МБ (лучше 88% / 71%).

class Solution:
 def longestValidParentheses(self, S: str) -> int:
     stack, ans = [-1], 0
     for i in range(len(S)):
         if S[i] == ‘(‘: stack.append(i)
         elif len(stack) == 1: stack[0] = i
         else:
              stack.pop()
              ans = max(ans, i — stack[-1])
      return ans

Код Java:

Наилучший результат для приведенного ниже кода — 2 мс / 38,7 МБ (лучше 69% / 94%).

class Solution {
   public int longestValidParentheses(String S) {
      Stack<Integer> stack = new Stack<>();
      stack.push(-1);
      int ans = 0;
      for (int i = 0; i < S.length(); i++)
          if (S.charAt(i) == ‘(‘) stack.push(i);
          else {
              stack.pop();
              if (stack.isEmpty()) stack.push(i);
              else ans = Math.max(ans, i — stack.peek());
          }
     return ans;
     }
}

Код C++:

Наилучший результат для приведенного ниже кода — 0 мс / 7,1 МБ (лучше, чем 100 % / 71 %).

class Solution {
public:
   int longestValidParentheses(string S) {
       vector<int> stack = {-1};
       int ans = 0;
       for (int i = 0; i < S.size(); i++)
           if (S[i] == '(') stack.push_back(i);
           else if (stack.size() == 1) stack[0] = i;
           else {
                 stack.pop_back();
                 ans = max(ans, i - stack.back());
           }
       return ans;
    }
};

Спасибо за чтение до сих пор. Я новенький здесь. Надеюсь, вы получили то, за чем пришли. Пожалуйста, оцените, если вам понравилось. Следуйте за мной для получения дополнительной информации. Помогите мне с обратной связью, комментируя обзор.