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...
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
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.