Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Maximum Nesting Depth Of The Parentheses

Easy
0/40
Average time to solve is 14m
profile
Contributed by
90 upvotes

Problem statement

You are given a string 'S' of length 'N' representing an integer.


A string is a valid parenthesis if it satisfies one of the following conditions:

If the string is empty or consists of a character other than ‘(‘ and ')'.

If the string can be represented as a concatenation of two strings such that both strings are valid parentheses strings.

If the string can be represented as '(A)', where A is a valid parenthesis.


Depth of a string is defined as follows:

depth( '' )=0

depth( A )=0, where ‘A’ is an empty string or consists of a character other than ‘(‘ and ‘)’.

depth( A+B )=max(depth( A ), depth( B )), such that ‘A’ and ‘B’ are both strings are valid parentheses strings.

depth( (A) ) = 1+depth(A), where ‘A’ is a valid parentheses string.


Given a valid parentheses string ‘S’, you must return the nesting depth of the string ‘S’.


Example:

Input:
S = '1+(3*6+(9-3))', N=13
Output: 2

Explanation: The digits 9 and 3 are inside of 2 nested parentheses. Hence we return 2.
Detailed explanation ( Input/output format, Notes, Images )
Input Format:
The first line of the input will contain an integer ‘N’ denoting the length of the string ‘S’.
The next line contains the string ’S’.
Output Format:-
The only line contains the nesting depth of string ‘S’.
Note:-
You don’t need to print anything. Just implement the given function.
Sample Input 1:
15
(3*(4*(5*(6))))
Sample Output 1:
4
Explanation Of Sample Input 1:
Input:
S = '(3*(4*(5*(6))))', N = 15
Output: 4

Explanation: The digit 6 is inside of 4 nested parentheses. Hence we return 4.
Sample Input 2:
11
(((((5)))))    
Sample Output 2:
5
Constraints:
1 <= N <= 10^5
’S’ consist of digits from 0 to 9 and characters ‘+’, ‘-’, ‘*’, ‘/’, ‘(’ and ‘)’.

Time Limit: 1 sec
Follow Up:
Can you solve this in O(N) time?
Hint

Mimic the use of stack using a count variable.

Approaches (1)
Iteration

Approach: 

 

  • We will iterate over the characters of ‘S’, and for each opening parentheses '(', increment a variable ‘maxNestingDepth’ by 1 and find the depth of the rest of the strings.
  • The value of the ‘maxNestingDepth’ will determine the following:
    • The number of open parentheses that are not yet closed.
    • The current depth of the parentheses.

 

Algorithm:

 

Function int maxDepth(string S):

  1. Initialize two integer variables, ‘maxNestingDepth’ and ‘currentDepth’, with 0.
  2. For each character ‘c’ in ‘S’:
    1. If ‘c’ equals ’(’:
      1. Increment ‘currentDepth’ by one.
      2. ‘maxNestingDepth’ is updated with a maximum of ‘maxNestingDepth’ and ‘currentDepth’.
    2. Else:
      1. Decrement ‘currentDepth’ by one.
  3. Return ‘maxNestingDepth’.
Time Complexity

O(N), Where ‘N’ is the string ‘S’ length. 

 

We are iterating over the length ‘N’ string, which takes an O(N) time complexity. Hence, the overall time complexity will be O(N). 

Space Complexity

O(1). 

 

We are taking O(1) extra space for storing the variables. Hence, the overall space complexity will be O(1).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Maximum Nesting Depth Of The Parentheses
All tags
Sort by
Search icon

Interview problems

Easiest solution

int maxDepth(string s) {

    // Write your code here.

    int count=0;

    int m=0;

    for(int i=0;i<s.length();i++)

    {

        if(s[i]=='(')

        {

            count++;

            m=max(m,count);

        }

        if(s[i]==')')

        {// checking valid parenthesis

            count--;

        }

    }

    return m-count; //max opened- not valid parenthesis

}

 

128 views
0 replies
0 upvotes

Interview problems

java solution

public class Solution {

    public static int maxDepth(String s) {

     

     int count=0;

     int max=Integer.MIN_VALUE;

     for(int i=0;i<s.length();i++){

        if(s.charAt(i)=='('){

            count++;

            max=Math.max(max,count);

        }

        if(s.charAt(i)==')'){

            count--;

        }

     }

     return  max;

    }

}

    

147 views
0 replies
2 upvotes

Interview problems

sol

int maxDepth(string s) {

    int max_depth = 0;

    int current_depth = 0;

 

    for (char c : s) {

        if (c == '(') {

            current_depth++;

            max_depth = max(max_depth, current_depth);

        } else if (c == ')') {

            if (current_depth > 0) {

                current_depth--;

            } else {

                // Handle the case when ')' is encountered before '('

                return -1;  // Invalid input

            }

        }

    }

 

    return max_depth;

}

 

99 views
0 replies
0 upvotes

Interview problems

best C++ sol

int maxDepth(string s) {

    // Write your code here.

    int count=0;

    int maxi=0;

    for(int i=0;i<s.length();i++)

    {

        if(s[i] == '('){

            count++;

            maxi = max(count,maxi);

        }

 

        

        if(s[i] == ')'){

            count--;

        }

        

    }

    return maxi;

}

 

852 views
2 replies
0 upvotes

Interview problems

simple and optimal solution with O(1)-space complexity && O(n)-time complexity.......

#include<bits/stdc++.h>

 

int maxDepth(string s) {

    // Write your code here.

    int count=0;

    int maxi=0;

    

    for(int i=0;i<s.length();i++){

         

          if(s.at(i)=='(')

            count++;

          else if(s.at(i)==')')

          count--; 

          maxi=max(maxi,count);   

          

    }

    return maxi;

    

}

 

628 views
1 reply
0 upvotes

Interview problems

Python Solution

def maxDepth(s:str) -> int:
    # Write your code here.
    count = 0
    max_count = 0
    for i in s:
        if  i == '(':
            count+=1
            max_count = max(max_count,count)
        elif i == ')':
            count -= 1
    return max_count
207 views
0 replies
0 upvotes

Interview problems

easy cpp solution no data struture used

int maxDepth(string s) {

    int n=s.length();

    int count=0;

    int maxi=0;

    for(int i=0;i<n;i++){

        if(s[i]=='('){

            count++;

        }

        if(s[i]>0 && s[i]>10){

            maxi=max(count,maxi);

            

        }

        if(s[i]==')'){

            count--;

        }

    }

    return maxi;

}

 

282 views
0 replies
0 upvotes

Interview problems

0(n) time complexity

public class Solution {

    public static int maxDepth(String s) {

        // Write your code here.

        int n=s.length();

 

         int count=0;

 

         int max=Integer.MIN_VALUE;

 

        for(int i=0;i<n;i++){

 

       if(s.charAt(i)=='(') {

 

        count++;

 

      max=Math.max(max, count);

 

     }

     if(s.charAt(i)==')') {

 

        count--;

 

}

        }

 

return max;

 

}

    }

318 views
0 replies
0 upvotes

Interview problems

Java Solution of O(n) TC

public static int maxDepth(String s) {

// Write your code here.

char ch='(';

int count=0;

int max=Integer.MIN_VALUE;

for(int i=0;i<s.length();i++){

if(s.charAt(i)==ch) {

count++;

max=Math.max(max, count);

}

 

if(s.charAt(i)==')'){

count--;

 

}

}

return max;

}

java

programming

253 views
0 replies
1 upvote

Interview problems

java solution

import java.util.*;

public class Solution {

    public static int maxDepth(String s) {

        // Write your code here.

        int max = 0;

        int curr = 0;

        int n = s.length();

        for(int i = 0; i < n;i++){

            char c = s.charAt(i);

            if(c == '('){

                curr++;

                max = Math.max(max, curr);

            }

            else if(c == ')'){

                curr--;

            }

        }

        return max;

    }

}

135 views
0 replies
0 upvotes
Full screen
Console