Search⌘ K
Home
Courses
Data Structures & Algorithms In Go

Solution Review: Longest Continuous Balanced Parenthesis

Explore the method to identify the longest continuous balanced parenthesis sequence using a stack in Go. Understand how to track sequences and update lengths efficiently within linear time.

We'll cover the following...

Solution

We keep track of the longest balanced parenthesis in the stack and update the length variable if we find a sequence greater than the previous one.

Go (1.6.2)
package main
import "fmt"
func longestContBalParen(str string, size int) int {
    stk := new(Stack)
    stk.Push(-1)
    length := 0
    for i := 0; i < size; i++ {
        if (str[i] == '(') {
            stk.Push(i)
        } else // string[i] == ')'
        {
            stk.Pop()
            if (stk.Length() != 0) {
                if length < i - stk.Top(){
                    length = i - stk.Top()
                }
            } else {
                stk.Push(i)
            }
        }
    }
    return length
}
// Testing code
func main() {
  expn := "())((()))(())()(()"
  size := len(expn)
  value :=longestContBalParen(expn, size)
  fmt.Println("longestContBalParen :: " , value)
}

Time complexity

The time complexity of this solution is ...