712224. Outermost Parentheses
Easy
Outermost Parentheses
Summary
Find the outermost parentheses in a given string. The string may contain multiple sets of parentheses, but you need to find the ones that are at the "outermost" level, i.e., not nested inside any other parentheses.
Detailed Explanation
The problem involves manipulating a string to extract the outermost parentheses. One approach is to iterate through the string and keep track of the opening and closing parenthesis counts. When the counts match, it means we've reached the outermost level, so return the current position.
Here's the step-by-step breakdown:
- Initialize two variables:
open_countto count the number of opening parentheses andclose_countto count the number of closing parentheses. - Iterate through the string:
- When an opening parenthesis is encountered, increment
open_count. - When a closing parenthesis is encountered, decrement
close_count.
- When an opening parenthesis is encountered, increment
- When
open_countandclose_countmatch for the first time (i.e., they both equal 0), it means we've reached the outermost level. - Return the position of the matching parentheses as the result.
Time complexity: O(n), where n is the length of the input string, since we iterate through the string once. Space complexity: O(1), since we only use a constant amount of space to store the counts and return value.
Optimized Solutions
Java
public int outermostParentheses(String s) {
int open_count = 0;
int close_count = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
open_count++;
} else if (c == ')') {
close_count++;
}
if (open_count == close_count && open_count > 0) {
return i;
}
}
return -1; // not found
}