Given a string s. Write the code to print the maximum depth of nested parenthesis in the given string.
Table of Contents
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
- Initialize a string s of length n.
- Create a stack to store parenthesis and two variables to store the maximum value and current maximum value and set their values as 0.
- 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.
- 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.
- If the stack is not empty, return -1.
- 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.
Auxiliary Space: O(n) because we used space in the stack to store the n characters.
Without Using Stack
Algorithm
- Initialize a string s of length n.
- Create two variables to store the maximum value and current maximum value and set their values as 0.
- 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.
- Else if the current character is a closing parenthesis, decrement the current maximum value if it is greater than 0 else return -1.
- If the current maximum value is not equal to 0, return -1.
- 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.
Auxiliary Space: O(1) because we used constant extra space.