Home » Technical Interview Questions » Stack Interview Questions » Find Maximum Depth of Nested Parenthesis in a String

Find Maximum Depth of Nested Parenthesis in a String


Difficulty Level Medium
Frequently asked in Amazon Facebook
Stack String

Given a string s. Write the code to print the maximum depth of nested parenthesis in the given string.

Find Maximum Depth of Nested Parenthesis in a String

Example

Input : s = “( a(b) (c) (d(e(f)g)h) I (j(k)l)m)”

Output : 4

Input : s = “( p((q)) ((s)t) )”

Output : 3

Using Stack

Algorithm

  1. Initialize a string s of length n.
  2. Create a stack to store parenthesis and two variables to store the maximum value and current maximum value and set their values as 0.
  3. Traverse through the string and check if the current character is an opening parenthesis, push it in the stack and increment the current maximum value. If the current maximum value is greater than the maximum value, update the maximum value as the current maximum value.
  4. Else if the current character is a closing parenthesis, pop the top character of the stack. Check if the current maximum value is greater than 0 and popped character is an opening parenthesis, decrement the current maximum value else return -1.
  5. If the stack is not empty, return -1.
  6. Else return the maximum value.

C++ Program to find maximum depth of nested parenthesis in a string

#include <bits/stdc++.h> 
using namespace std; 

class Stack{  
    public: 
        int top;  
        unsigned capacity;  
        char* array;  
};  
  
Stack* createStack(unsigned capacity){  
    Stack* stack = new Stack(); 
    stack->capacity = capacity;  
    stack->top = -1;  
    stack->array = new char[(stack->capacity * sizeof(char))];  
    return stack;  
}  
  
int isFull(Stack* stack){ 
    return stack->top == stack->capacity - 1; 
}  
  
int isEmpty(Stack* stack){ 
    return stack->top == -1;
}  
  
void push(Stack* stack, char item){  
    if(isFull(stack))  
        return;  
    stack->array[++stack->top] = item;  
}  
  
char pop(Stack* stack){  
    if(isEmpty(stack))  
        return -1;  
    return stack->array[stack->top--];  
}  

int maxDepth(string s){ 
    int n = s.length();  
    Stack* stack = createStack(n);
    int current_max = 0; 
    int max = 0;   
  
    for(int i = 0; i<n; i++){
        
        if(s[i] == '('){ 
            push(stack, s[i]);
            current_max++; 
  
            if(current_max > max){ 
                max = current_max;
            }    
        } 
        
        else if(s[i] == ')'){ 
            char c = pop(stack);
            if((current_max > 0) && (c == '(')){ 
                current_max--; 
            }    
            else{
                return -1;
            }    
        } 
    } 
  
    if(!isEmpty(stack)){ 
        return -1; 
    }    
  
    return max; 
} 
  
int main(){
    
    string s = "( a(b) (c) (d(e(f)g)h) I (j(k)l)m)"; 
    cout<<maxDepth(s); 
    
    return 0; 
}
4

Java Program to find maximum depth of nested parenthesis in a string

import java.util.*; 
  
class Stack{ 
    int size; 
    int top; 
    char[] a;  
  
    boolean isEmpty(){ 
        return(top < 0); 
    } 
      
    Stack(int n){ 
        top = -1; 
        size = n; 
        a = new char[size]; 
    } 
  
    boolean push(char x){ 
        if (top >= size){ 
            System.out.println("Stack Overflow"); 
            return false; 
        } 
        else{ 
            a[++top] = x; 
            return true; 
        } 
    } 
  
    char pop(){ 
        if(top < 0){ 
            System.out.println("Stack Underflow"); 
            return 0; 
        } 
        else{ 
            char x = a[top--]; 
            return x; 
        } 
    } 
}

class Depth{
    
    static int maxDepth(String s){
        
        int current_max = 0;
        int max = 0; 
        int n = s.length(); 
        Stack stack = new Stack(n);
  
        for(int i = 0; i < n; i++){ 
            if(s.charAt(i) == '('){ 
                current_max++; 
                stack.push(s.charAt(i));
  
                if(current_max > max){ 
                    max = current_max; 
                } 
            } 
            else if(s.charAt(i) == ')'){ 
                
                char c = stack.pop();
                
                if((current_max > 0) && (c == '(')){ 
                    current_max--; 
                } 
                else{ 
                    return -1; 
                } 
            } 
        } 
  
        if(!stack.isEmpty()){ 
            return -1; 
        } 
  
        return max; 
    } 
  
    public static void main(String[] args){
        
        String s = "( a(b) (c) (d(e(f)g)h) I (j(k)l)m)"; 
        System.out.println(maxDepth(s)); 
        
    } 
}
4

Complexity Analysis

Time Complexity: O(n) where n is the size of the string.

READ  Balanced Expression with Replacement

Auxiliary Space: O(n) because we used space in the stack to store the n characters.

Without Using Stack

Algorithm

  1. Initialize a string s of length n.
  2. Create two variables to store the maximum value and current maximum value and set their values as 0.
  3. Traverse through the string and check if the current character is an opening parenthesis, increment the current maximum value. If the current maximum value is greater than the maximum value, update the maximum value as the current maximum value.
  4. Else if the current character is a closing parenthesis, decrement the current maximum value if it is greater than 0 else return -1.
  5. If the current maximum value is not equal to 0, return -1.
  6. Else return the maximum value.

C++ Program to find maximum depth of nested parenthesis in a string

#include <iostream> 
using namespace std; 
  
int maxDepth(string s){ 
    int current_max = 0; 
    int max = 0;   
    int n = s.length(); 
  
    for(int i = 0; i<n; i++){ 
        if(s[i] == '('){ 
            current_max++; 
  
            if(current_max > max){ 
                max = current_max;
            }    
        } 
        else if(s[i] == ')'){ 
            if(current_max > 0){ 
                current_max--; 
            }    
            else{
                return -1;
            }    
        } 
    } 
  
    if(current_max != 0){ 
        return -1; 
    }    
  
    return max; 
} 
  
int main(){
    
    string s = "( a(b) (c) (d(e(f)g)h) I (j(k)l)m)"; 
    cout<<maxDepth(s); 
    
    return 0; 
}
4

Java Program to find maximum depth of nested parenthesis in a string

class Depth{
    
    static int maxDParenthesis(String s){
    
        int currentmax = 0;
        int max = 0; 
        int n = s.length(); 
  
        for(int i = 0; i < n; i++){ 
            if(s.charAt(i) == '('){ 
                currentmax++; 
  
                if(currentmax > max){ 
                    max = currentmax; 
                } 
            } 
            else if(s.charAt(i) == ')'){ 
                if(currentmax > 0){ 
                    currentmax--; 
                } 
                else{ 
                    return -1; 
                } 
            } 
        } 
    
        if(currentmax != 0){ 
            return -1; 
        } 
        
        return max; 
    } 
    
    public static void main(String[] args){
    
        String s = "( a(b) (c) (d(e(f)g)h) I (j(k)l)m)";
        
        System.out.println( maxDParenthesis(s) ); 
    
    } 
}
4

Complexity Analysis

Time Complexity: O(n) where n is the size of the string.

READ  Iterative Tower of Hanoi

Auxiliary Space: O(1) because we used constant extra space.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!! You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Anisha was able to crack Amazon after practicing questions from TutorialCup