301. Remove Invalid Parentheses

https://leetcode.com/problems/remove-invalid-parentheses/submissions/1

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).
Example 1:
Input: "()())()"
Output: ["()()()", "(())()"]
Example 2:
Input: "(a)())()"
Output: ["(a)()()", "(a())()"]
Example 3:
Input: ")("
Output: [""]
  • If there are repeated open/close parentheses only remove one of them
  • If the current state will not yield a solution (number of open parentheses so far < 0) stop iterating
  • Remember open parentheses count so we don't have to calculate it again
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

void remove(int open, int left, int right, int iStart, string s, vector<string> &out) {
        // Iterate through all the remaining characters and see if we can remove them
        // In the meantime we can also keep track of how many open parantheses we have
        // so far to avoid calculating it separately.
        for (int i = iStart; i < s.size() && open >= 0; ++i) {
            if (s[i] == '(') {
                // If we should remove this open parantheses, make sure last element wasn't an
                // open parantheses since removing this would result in the same output
                // as removing the previous one so it's redundant.
                if (left > 0 && (i == 0 || s[i - 1] != '('))
                    remove(open, left - 1, right, i, s.substr(0, i) + s.substr(i + 1), out);

                ++open;
            } else if (s[i] == ')') {
                // Same as open parantheses, don't remove if same as previous character
                if (right > 0 && (i == 0 || s[i - 1] != ')'))
                    remove(open, left, right - 1, i, s.substr(0, i) + s.substr(i + 1), out);

                --open;
            }
        }

        if (left == 0 && right == 0 && open == 0)
            out.emplace_back(move(s));
}

vector<string> removeInvalidParentheses(string s) {
        vector<string> out;

        // How many left and right parantheses should we remove?
        int left = 0, right = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(') {
                ++left;
            } else if (s[i] == ')') {
                if (left > 0)
                    --left;
                else
                    ++right;
            }
        }
        cout << left <<  " ";
        cout << right << endl;
        remove(0, left, right, 0, s, out);
        return out;
 }

int main()
{
   vector<string> str= removeInvalidParentheses("()())()");
    //cout << str;
   for (const auto i: str)
    std::cout << i << ' ';
    return 0;
}

Comments

Post a Comment

Popular posts from this blog

Ace the Amazon Interview

Image
Ace the Amazon Interview Below are some tips we hope you will find helpful in preparing for your meetings with our team. Dress Code Our dress code at Amazon is relaxed, so we encourage you to dress comfortably in business casual attire. At work, you’ll find most engineers in t-shirts and jeans. No suits please. Company Background Know what interests you about Amazon and the team or teams you will be interviewing with. It may help to spend some time researching our specific products and features, as well as our competitors. Knowing about our product groups and how they all interact with each other will give you context around our roles and will likely prompt deeper conversations that will hopefully provide a richer interview experience. Refer back to the team link(s) I sent in my first few emails. Event Format You will meet 1:1 with several Amazonians. The interviewer team will be comprised of Software Development Managers and Senior Engineers. Each inte...
Read more

Map in c++

map : A collection that stores pairs where each pair consists of a first half called a key and second half called a vlues. - sometimes called a "dictionary","associative array", or "hash" - usage: add(key,value) pairs; look up a values by supplying a key. real-world examples:  - dictionary of words and definations  - phone book  - social buddy list. Map Opration m.put(key.value) : adds key/value pair to the map. m.get(key): returns the value paired with the given key. m.remove(key): removes the given key and its paired value. Map Vs HashMap Map - implemented using a linked structure called binary search tree.  -  pretty fast for all operations; keys are stored in sorted order.  - both kinds of maps implement exactly the same operations. HashMap - implemented using a special array called a hash table.  - very fast but keys are stored in unpredictable order.
Read more

Google Interview Preparation

The software design process boils down to 4 main steps, this interview process is looking for you to show those things. Requirements -  Ask clarifying question The requirements given are usually vague. The problem to solve isn't the one given. It's the one in your head. People typically prepare with hackerrank or leetcode where they have to specify the problem clearly and with all of the test cases right away because you can't ask any questions. That isn't true in an interview. Ask questions! Test -  Show it works If you can't determine the input output of your test cases before you start designing you likely don't know what your supposed to be writing yet. Thinking about corner cases and potential pitfalls before you start will save a lot of time. It also forces you to run the program you're about to write in your brain first giving you a better intuitive understanding of your approach. Design -  Explain your algorithm This lets you show...
Read more