[LeetCode / C++] 1249. Minimum Remove to Make Valid Parentheses

1. Question

Given a string s of '(' , ')' and lowercase English characters.

Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

It is the empty string, contains only lowercase characters, or
It can be written as AB (A concatenated with B), where A and B are valid strings, or
It can be written as (A), where A is a valid string.

Example 1:

Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
Explanation: "lee(t(co)de)" , "lee(t(c)ode)" would also be accepted.

Example 2:

Input: s = "a)b(c)d"
Output: "ab(c)d"

Example 3:

Input: s = "))(("
Output: ""
Explanation: An empty string is also valid.

2. Thoughts

3. Tips learned

3.1. Stack

In C++, a stack can be implemented using the Standard Template Library (STL), specifically by using the std::stack container. Here’s a quick guide on how to use a stack in C++:

1. Including the Necessary Header

First, you need to include the header file that defines the std::stack class.

#include <iostream>
#include <stack>

2. Creating a Stack

You can create a stack that holds any data type. Here's how to create a stack of integers:

std::stack<int> myStack;

3. Basic Operations

Here are the common stack operations you can perform:

• Pushing an element onto the stack:

  myStack.push(10);  // pushes 10 onto the stack

• Popping an element from the stack:

  myStack.pop();  // removes the top element from the stack

• Accessing the top element:

  int topElement = myStack.top();  // gets the top element of the stack

• Checking if the stack is empty:

  if(myStack.empty()) {
      std::cout << "Stack is empty" << std::endl;
  }

• Getting the size of the stack:

  std::cout << "Stack size: " << myStack.size() << std::endl;

4. Complete Example

Here is a full example demonstrating the basic stack operations:

#include <iostream>
#include <stack>

int main() {
    std::stack<int> myStack;

    // Push elements
    myStack.push(10);
    myStack.push(20);
    myStack.push(30);

    // Access the top element
    std::cout << "Top element: " << myStack.top() << std::endl;

    // Pop the top element
    myStack.pop();
    std::cout << "Top element after pop: " << myStack.top() << std::endl;

    // Stack size
    std::cout << "Stack size: " << myStack.size() << std::endl;

    // Check if the stack is empty
    if(myStack.empty()) {
        std::cout << "Stack is empty" << std::endl;
    } else {
        std::cout << "Stack is not empty" << std::endl;
    }

    return 0;
}

5. Stack Characteristics

• LIFO (Last In, First Out): The stack works in a LIFO manner, meaning the last element pushed into the stack will be the first one to be popped out.
• Dynamic Size: The stack dynamically adjusts its size based on the elements pushed or popped.

This should give you a good starting point to use stacks in C++.

3.2. Remove char in string

Yes, you can remove a character from a string in C++. There are a few different ways to remove a character from a string depending on your specific use case. Below are some methods you can use:

1. Using erase Method

You can use the erase method to remove a specific character at a given index.

Example: Removing a character by position

#include <iostream>
#include <string>

int main() {
    std::string str = "Hello World";
    
    // Remove the character at index 5 (space in this case)
    str.erase(5, 1);  // Syntax: str.erase(position, length)

    std::cout << "String after removal: " << str << std::endl;  // Output: "HelloWorld"
    return 0;
}

2. Using erase with remove

You can remove all occurrences of a particular character using the std::remove function combined with erase.

Example: Removing all occurrences of a specific character

#include <iostream>
#include <string>
#include <algorithm>  // For std::remove

int main() {
    std::string str = "Hello World";

    // Remove all occurrences of 'l'
    str.erase(std::remove(str.begin(), str.end(), 'l'), str.end());

    std::cout << "String after removal: " << str << std::endl;  // Output: "Heo Word"
    return 0;
}

4. My solution

class Solution
{
public:
    string minRemoveToMakeValid(string s)
    {
        stack<int> stck;

        for (int i = 0; i < s.length(); i++)
        {
            if (s[i] == '(')
            {
                stck.push(i);
            }
            else if (s[i] == ')')
            {
                if (stck.empty())
                {
                    s[i] = '.';
                }
                else
                {
                    stck.pop();
                }
            }
        }

        while (!stck.empty())
        {
            s[stck.top()] = '.';
            stck.pop();
        }

        s.erase(remove(s.begin(), s.end(), '.'), s.end());

        return s;
    }
};

62/62 cases passed (10 ms)
Your runtime beats 99.59 % of cpp submissions
Your memory usage beats 90.68 % of cpp submissions (12 MB)

5. AI Solution and Improvements

Your current solution is already well-structured and efficient, but there are a few improvements that can be made to enhance readability and make the code more idiomatic in C++.

Suggestions for Improvement:

1. Use range-based for loops: This is more C++-style for iterating over the characters in the string when applicable, although we still need indices for this specific case.
2. Simplify variable names: Using more meaningful variable names can improve readability.
3. Minimize character marking: Instead of using . to mark invalid parentheses, consider using a set to store indices for removal.
4. Optimize the second pass: Instead of looping through the stack again to remove extra parentheses, use a single pass to identify both open and unmatched parentheses.

Improved Solution

#include <iostream>
#include <stack>
#include <string>
#include <algorithm> // for std::remove

class Solution {
public:
    std::string minRemoveToMakeValid(std::string s) {
        std::stack<int> openParentheses;
        
        // First pass: mark invalid parentheses
        for (int i = 0; i < s.length(); ++i) {
            if (s[i] == '(') {
                openParentheses.push(i);
            } else if (s[i] == ')') {
                if (openParentheses.empty()) {
                    s[i] = '*'; // Mark invalid closing parentheses
                } else {
                    openParentheses.pop(); // Matched parentheses
                }
            }
        }

        // Mark unmatched opening parentheses
        while (!openParentheses.empty()) {
            s[openParentheses.top()] = '*'; // Mark invalid opening parentheses
            openParentheses.pop();
        }

        // Second pass: remove marked characters
        s.erase(std::remove(s.begin(), s.end(), '*'), s.end());
        
        return s;
    }
};

Key Improvements:

1. Marked Characters: We use '*' to mark invalid parentheses, which makes it clearer that these characters will be removed. This avoids potentially clashing with other characters like ..

2. Efficiency: The use of std::remove and erase is already efficient, so I left that part as it is.

3. Stack Naming: The stack is now named openParentheses to make it more descriptive.

4. Final Erase: The string cleaning operation remains in place and is idiomatic for C++.

Time and Space Complexity:

• Time Complexity: O(n), where n is the length of the string. You make two passes over the string (one to mark invalid parentheses and one to erase them).
• Space Complexity: O(n) due to the stack used to track the indices of unmatched opening parentheses.