Sponsored
Sponsored
This approach utilizes a single counter to track the current depth of nesting while iterating through the string. Whenever an open parenthesis '(' is encountered, the counter is incremented, and whenever a closing parenthesis ')' is encountered, the counter is decremented. The maximum value of the counter at any point during the iteration is recorded as the maximum nesting depth.
Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1), as only a few variables are used.
1#include <iostream>
2#include <string>
3using namespace std;
4
5int maxDepth(string s) {
6 int current_depth = 0, max_depth = 0;
7 for (char c : s) {
8 if (c == '(') {
9 current_depth++;
10 max_depth = max(max_depth, current_depth);
11 } else if (c == ')') {
12 current_depth--;
13 }
14 }
15 return max_depth;
16}
17
18int main() {
19 string s = "(1+(2*3)+((8)/4))+1";
20 cout << "Max Depth: " << maxDepth(s) << endl;
21 return 0;
22}Using a similar logic as in C, this C++ solution uses a for-each loop to traverse each character. The logic of counting depth and updating the maximum depth is identical.
This approach uses a stack to simulate the depth of nested parentheses. Each time an open parenthesis '(' is encountered, it is pushed onto the stack, and for each closing parenthesis ')', an item is popped. The maximum size of the stack during this process reflects the maximum nesting depth.
Time Complexity: O(n). Space Complexity: O(n) due to stack usage.
1using System.Collections.Generic;
public class Solution {
public int MaxDepth(string s) {
Stack<char> stack = new Stack<char>();
int maxDepth = 0;
foreach (char c in s) {
if (c == '(') {
stack.Push(c);
maxDepth = Math.Max(maxDepth, stack.Count);
} else if (c == ')') {
if (stack.Count > 0) stack.Pop();
}
}
return maxDepth;
}
public static void Main(string[] args) {
Solution sol = new Solution();
string s = "(1+(2*3)+((8)/4))+1";
Console.WriteLine("Max Depth: " + sol.MaxDepth(s));
}
}The C# solution uses a stack from System.Collections.Generic to track depth and determine maximum depth the stack reaches through analyzing parentheses.