I am a bit puzzled by one exercise I recently came across with.

It seems like an easy task and I've put my solution but it turned out it didn't pass all the tests :D

In the example, I've found two example substrings:

Input: S = "(()("
Output: 2
Explanation: The longest valid 
substring is "()". Length = 2.

and

Input: S = "()(())("
Output: 6
Explanation: The longest valid 
substring is "()(())". Length = 6.

at the first glance, everything is clear.

I came up with my solution:

class Solution {

  findMaxLen(s) {
    if (!s || !s.length) throw new Error('Invalid input value provided')

    let openIndex = null
    let closingIndex = null

    for (let i = 0; i < s.length; i  ) {
      if (s[i] == '(' && !openIndex) openIndex = i   1
      if (s[i] == ')') closingIndex = i   1
    }

    if(!closingIndex || !openIndex) throw new Error('Invalid substring')

    return closingIndex - openIndex   1
  }
}

So, my solution should solve the issue of trying to find The longest substring with the opening and closing parentheses.

But it failed the test with an input value: (((() Where the correct answer is 2 and my output is 5

Is this (((() different from ()(())( one provided in the example?

I suppose I do not wholly understand the idea of what the substring is or something...

CodePudding user response：

This pseudocode should work. Some bugs or edge cases might have loose ends as I just wrote this here on the fly. Feel free to test it and point out the misses.

helper_stack = null
max_valid_len = 0
running_len = 0

for i=0 to input_s.length:
    if helper_stack.length == 0:
        if input_s[i] == ')':
            running_len = 0
            continue
        else:
            helper_stack.push('(')
    else:
        if input_s[i] == '(':
            helper_stack.push('(')
        else:
            helper_stack.pop()
            running_len  = 2
            if running_len > max_valid_len:
                max_valid_len = running_len

EDIT: Explanation

With your logic, you are not keeping track of order of opening and closing of brackets, which is important. If a closing bracket precedes open, string becomes invaid by default. Hence, using stack makes sense here.

If ever we encounter a closing bracket before open, we restart from that point. Hence, we set the running_len = 0. For every encounter of closing bracket, if an open bracket is there to balance it, we just pop it off, and since its a pair (of chars, when we consider length of string), running_len = 2 is done.

With little modification, we can even reproduce max_valid_substring if needed. However, in our case, we could even use just an integer instead of helper_stack. For every push('(') operation, just do var = 1, and var -= 1 for pop and that should also do the trick. Note that here, we are not explicitly using stack, but this is still conceptually LIFO = last in first out which is basically, stack.