Leetcode 1249: Minimum Remove to Make Valid Parentheses
You are given a string s containing lowercase English letters and parentheses. Your task is to remove the minimum number of parentheses to make the string valid.
Problem
Approach
Steps
Complexity
Input: The input consists of a string s that contains parentheses and lowercase English letters.
Example: s = "abc(de(f)gh)"
Constraints:
• 1 <= s.length <= 10^5
• s[i] is either '(' , ')', or lowercase English letter
Output: Return the string after removing the minimum number of parentheses to make it valid.
Example: "abc(de(f)gh)"
Constraints:
• The output string should be valid after removing parentheses.
Goal: Ensure the string is valid by removing unnecessary parentheses.
Steps:
• Use a stack to track the indices of unmatched parentheses.
• Iterate through the string, removing parentheses that do not form a valid pair.
• Construct and return the new string without invalid parentheses.
Goal: The string is non-empty and can contain up to 100,000 characters.
Steps:
• 1 <= s.length <= 10^5
• s[i] is either '(' , ')', or lowercase English letter
Assumptions:
• The string contains only valid parentheses or lowercase English letters.
• Input: s = "abc(de(f)gh)"
• Explanation: The string is already valid, so no parentheses are removed.
• Input: s = "a)b(c)d"
• Explanation: The first ')' is removed to make the string valid, resulting in 'ab(c)d'.
• Input: s = "))(("
• Explanation: All parentheses are removed, leaving an empty string, which is valid.
Approach: The solution involves using a stack to track unmatched parentheses and iterating over the string to remove invalid ones.
Observations:
• The problem requires finding invalid parentheses and removing them.
• A stack is a natural data structure for this type of matching problem.
• We can process the string and ensure parentheses are balanced by using a stack to track unmatched opening parentheses and their indices.
Steps:
• Initialize a stack to store indices of unmatched parentheses.
• Traverse the string and push the indices of '(' onto the stack.
• For each ')', check if it forms a valid pair with a previous '(' (using the stack). If not, mark it for removal.
• After processing the string, construct the final string by skipping indices of unmatched parentheses.
Empty Inputs:
• If the string is empty, the result is also empty.
Large Inputs:
• The algorithm should efficiently handle strings of size up to 100,000.
Special Values:
• If there are no parentheses in the string, return the original string.
Constraints:
• Ensure the algorithm works within the given time complexity constraints for large inputs.
string minRemoveToMakeValid(string s) {
vector<int> stk, itk;
for(int i = 0; i < s.length(); i++) {
char a = s[i];
if(a == '(') { stk.push_back(i); }
else if(a == ')') {
if(stk.size() == 0) stk.push_back(i);
else if(s[stk.back()] == '(') stk.pop_back();
else stk.push_back(i);
}
}
string res = "";
set<int> st(stk.begin(), stk.end());
for(int i = 0; i < s.length(); i++) {
if(st.count(i)) continue;
res += s[i];
}
return res;
}
1 : Function Definition
string minRemoveToMakeValid(string s) {
This is the function definition of `minRemoveToMakeValid`, which takes a string `s` as input and returns a modified string with the minimum number of parentheses removed to make it valid.
2 : Variable Initialization
vector<int> stk, itk;
Two vectors, `stk` and `itk`, are initialized. `stk` will store the indices of unmatched parentheses, and `itk` is unused in this implementation.
3 : Loop Through String
for(int i = 0; i < s.length(); i++) {
A loop is used to iterate through each character of the string `s`. The loop index `i` is used to access each character.
4 : Character Assignment
char a = s[i];
The current character `a` is assigned the value of the character at position `i` in the string `s`.
5 : Handle Opening Parenthesis
if(a == '(') { stk.push_back(i); }
If the current character is an opening parenthesis '(', its index is pushed onto the `stk` vector to track its position.
6 : Handle Closing Parenthesis
else if(a == ')') {
If the current character is a closing parenthesis ')', we check if there is an unmatched opening parenthesis.
7 : Handle Unmatched Closing Parenthesis
if(stk.size() == 0) stk.push_back(i);
If the `stk` is empty, meaning there is no corresponding opening parenthesis for this closing parenthesis, its index is added to `stk`.
8 : Match Parentheses
else if(s[stk.back()] == '(') stk.pop_back();
If the last element in `stk` corresponds to an opening parenthesis, it is removed (the parentheses are matched).
9 : Unmatched Closing Parenthesis
else stk.push_back(i);
If the current closing parenthesis cannot be matched with the last opening parenthesis, its index is added to `stk`.
10 : Initialize Result String
string res = "";
A string `res` is initialized to store the final result after removing the invalid parentheses.
11 : Create Set from Stack
set<int> st(stk.begin(), stk.end());
A set `st` is created from the `stk` vector to efficiently check if an index is in the list of invalid parentheses.
12 : Loop Through String Again
for(int i = 0; i < s.length(); i++) {
Another loop is used to iterate through the string `s` and build the result string by excluding the indices stored in `st`.
13 : Check Invalid Indices
if(st.count(i)) continue;
If the current index `i` is found in the set `st` (meaning it corresponds to an invalid parenthesis), skip it and continue with the next character.
14 : Build Result String
res += s[i];
If the current index `i` is valid, append the character at index `i` to the result string `res`.
15 : Return Statement
return res;
Return the result string `res`, which now contains the valid string with the minimum number of parentheses removed.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The algorithm processes the string once, so the time complexity is O(n), where n is the length of the string.
Best Case: O(n)
Worst Case: O(n)
Description: In the worst case, all parentheses could be unmatched, so the space complexity is O(n).
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus