[Programming Problem] Minimum Remove to Make Valid Parentheses

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.

Example 4:
Input: s = “(a(b(c)d)”
Output: “a(b(c)d)”

[Problem Link]

Initial thought was do a BFS search where each outgoing node is the string without a bracket. At any level if we find a solution, we stop there (for e.g. in below example we would stop at Level 1 itself since we find “ab(c)d”).

                         "a)b(c)d"
 
        "ab(c)d" ✔️      "a)bc)d"      "a)b(cd"
 
  "abc)d"   "ab(cd"        ...           ...

However, above solution will time out.

Instead we use the stack data structure to determine the brackets that cause invalidity of parentheses. These are simply the brackets remaining in the stack (at the end of validity test). With the bracket, we also store the index of the bracket (in the string) which makes it quicker to delete characters from those positions and rebuild valid string.

/**
 * @param {string} s
 * @return {string}
 */
 
// Node representing bracket and its index (in the string)
var Node = function(c, idx) {
    this.c = c;
    this.idx = idx;
}
 
var minRemoveToMakeValid = function(s) {
    let sChars = Array.from(s);
 
    // Use a stack to determine which brackets are causing 'invalidity'
    // We use Node data strcuture so that we know its index's (which makes it easy to remove)
    let stk = [];
    for ( let i = 0 ; i < sChars.length ; i++ ) {
        let curr = new Node(sChars[i], i);
        if ( curr.c === '(' || (curr.c === ')' && stk.length === 0) ) {
            stk.push(curr);
        } else if ( curr.c === ')' ) {
            let prev = stk.pop();
            if ( prev.c === ')' ) {
                stk.push(prev);
                stk.push(curr);
            }
        }
    }
 
    // index'es which we need to remove
    let toDelete = stk.map(function(n) {
        return n.idx;
    });
 
    // build new string!
    let newS = '';
    for ( let i = 0 ; i < sChars.length ; i++ ) {
        if (toDelete.includes(i)) continue;
        newS += sChars[i];
    }
 
    return newS;
};

1,634 thoughts on “[Programming Problem] Minimum Remove to Make Valid Parentheses

  1. I must express my gratitude for your generosity for those who actually need help with the situation. Your personal commitment to passing the message up and down had become remarkably significant and have all the time permitted others like me to realize their dreams. Your entire invaluable tips and hints entails a whole lot to me and substantially more to my mates. Thanks a ton; from each one of us.

  2. I want to get across my affection for your kindness supporting people who really need guidance on this niche. Your special commitment to getting the solution all through came to be surprisingly effective and have consistently permitted individuals much like me to realize their desired goals. Your own invaluable suggestions denotes a great deal to me and somewhat more to my colleagues. Best wishes; from each one of us.

  3. I have to convey my admiration for your kindness for folks who need help with in this matter. Your special commitment to passing the solution all around appeared to be extraordinarily invaluable and has enabled professionals just like me to achieve their objectives. Your own important guidelines indicates so much to me and much more to my office workers. Many thanks; from everyone of us.

  4. I definitely wanted to compose a simple comment in order to thank you for all the precious recommendations you are sharing on this site. My considerable internet look up has at the end of the day been recognized with good facts and strategies to write about with my neighbours. I would state that that most of us visitors are very fortunate to exist in a fine community with many special professionals with valuable concepts. I feel truly lucky to have encountered your entire website and look forward to so many more entertaining moments reading here. Thanks again for all the details.

  5. I wanted to post you a little note to thank you over again for these stunning views you’ve shown at this time. It has been so open-handed with you to provide without restraint just what many individuals could have advertised as an ebook to end up making some profit on their own, specifically considering the fact that you might have tried it in case you decided. These advice additionally worked to become a easy way to recognize that many people have the same zeal similar to my very own to grasp much more with regards to this condition. I am sure there are many more pleasant opportunities up front for individuals that scan your site.

  6. I have to point out my appreciation for your generosity in support of men who should have help on this particular issue. Your very own dedication to getting the message along appears to be particularly insightful and has specifically enabled many people much like me to achieve their ambitions. Your personal warm and friendly recommendations means a great deal to me and somewhat more to my office colleagues. Thank you; from each one of us.

  7. I must point out my appreciation for your generosity supporting men who absolutely need guidance on this subject. Your personal commitment to passing the message all over came to be certainly beneficial and have enabled regular people much like me to attain their pursuits. Your new useful facts can mean much to me and somewhat more to my colleagues. Thank you; from everyone of us.

  8. I wish to voice my appreciation for your kind-heartedness in support of people that must have help with that topic. Your very own dedication to passing the message all over had been pretty valuable and have in most cases encouraged people much like me to attain their targets. Your new valuable recommendations implies a great deal a person like me and even more to my fellow workers. Best wishes; from all of us.

  9. I simply wished to thank you so much all over again. I’m not certain what I would have taken care of in the absence of the creative ideas shown by you over such a area. It absolutely was a very frightful issue for me personally, nevertheless understanding the expert strategy you solved the issue took me to cry over fulfillment. I’m just thankful for the information and thus hope you really know what a great job your are undertaking instructing others through a web site. I know that you’ve never come across any of us.

  10. I must convey my admiration for your kindness supporting people who require help with this one subject matter. Your personal commitment to passing the message throughout appears to be amazingly informative and have without exception encouraged others like me to attain their pursuits. Your entire invaluable information entails this much a person like me and extremely more to my colleagues. Thank you; from each one of us.

  11. I precisely wanted to appreciate you again. I am not sure the things I might have implemented in the absence of those ideas shared by you concerning my concern. It actually was an absolute depressing scenario for me, but viewing this skilled style you resolved that forced me to cry with happiness. Now i’m happy for this information and expect you know what a great job you were putting in teaching other individuals via your site. Most probably you’ve never got to know any of us.

  12. I must point out my love for your kind-heartedness in support of people that really need help on that niche. Your real dedication to passing the solution around has been extraordinarily functional and has enabled many people just like me to get to their desired goals. Your invaluable help and advice can mean a whole lot to me and still more to my office colleagues. Thanks a ton; from all of us.

  13. I would like to get across my admiration for your kind-heartedness giving support to visitors who have the need for assistance with this one area. Your real commitment to passing the message throughout was unbelievably powerful and has all the time empowered folks like me to reach their dreams. Your personal valuable tips and hints can mean a lot a person like me and a whole lot more to my office colleagues. Regards; from each one of us.

  14. I have to express my love for your generosity supporting men and women who require help with the theme. Your real dedication to getting the solution around turned out to be unbelievably useful and has encouraged many people much like me to get to their objectives. Your own insightful hints and tips can mean this much a person like me and even more to my mates. With thanks; from everyone of us.

  15. I wanted to send you a tiny word to help thank you yet again for your personal awesome things you have provided above. It has been really generous with people like you to make freely just what a number of people might have sold for an ebook to generate some dough on their own, precisely considering the fact that you might well have done it in case you considered necessary. The basics in addition worked as a fantastic way to know that other people online have the identical interest the same as my personal own to know the truth a lot more with regard to this condition. I’m certain there are thousands of more fun moments ahead for individuals who read your site.

  16. |It is not important to be perfect when fashion is involved. Firstly, there is no such thing as perfection in this world. Also, if you try too hard, you may look uptight. Disheveled looks with messy hair, non-matching shoes, or not completely buttoned pieces like those of Kate Moss can look great.

  17. I have to get across my respect for your kind-heartedness giving support to people that should have help with that study. Your real dedication to getting the message all around had been remarkably effective and have frequently permitted men and women like me to get to their goals. This warm and helpful help means a great deal to me and substantially more to my office colleagues. Thank you; from each one of us.

  18. I would like to voice my passion for your kind-heartedness supporting individuals that need help on the idea. Your very own commitment to passing the message throughout became surprisingly advantageous and has usually empowered regular people just like me to realize their dreams. Your important recommendations implies a great deal to me and further more to my office colleagues. Regards; from each one of us.

  19. My spouse and i got now contented that Louis managed to complete his investigations through the precious recommendations he acquired out of the weblog. It is now and again perplexing just to happen to be releasing secrets and techniques other people may have been trying to sell. And we also keep in mind we have you to appreciate for this. These illustrations you made, the straightforward website navigation, the friendships you can make it easier to promote – it’s everything awesome, and it is leading our son in addition to our family believe that that theme is amusing, which is certainly highly mandatory. Many thanks for the whole lot!

  20. I intended to draft you a little observation just to thank you so much again for all the pleasant tricks you’ve documented at this time. This is certainly surprisingly open-handed with people like you to present without restraint exactly what a few people might have marketed for an electronic book to get some profit for themselves, notably now that you could possibly have done it if you ever considered necessary. The good tips also acted to become fantastic way to fully grasp other people have the same keenness just like my very own to find out whole lot more in regard to this condition. I think there are thousands of more pleasant moments up front for those who find out your website.

  21. Konkordato Konkordato Nedir Konkordato Projesi Konkordato Danışmanlığı Uzman Görüşü Mali Müşavir SPK Gayrimenkul Değerleme Uzmanı Uzman Mütalaası Yabancıya Satış SGK Sigorta prim borcu gayrimenkul değerleme raporu Vergi borcu gayrimenkul değerleme raporu Şahıs şirketi Makul Güvence Raporu Bağımsız Denetim Raporu Konkordato davası için dosya hazırlama Mali Müşavir

  22. Pingback: meritking
  23. Pingback: meritking
  24. Pingback: meritking
  25. Pingback: meritking
  26. Pingback: meritking
  27. Pingback: fuck
  28. Pingback: porn
  29. Pingback: child porn
  30. Pingback: child porn
  31. Pingback: porn
  32. Покупка диплома в Москве – это так обычное действие, какое заинтересовывает много людей – diplomsuper.net. В столице доступны множество опций для приобретения диплома.

  33. Pingback: grandpashabet
  34. Pingback: grandpashabet
  35. Sürekli güncellenen ve en son gelişmeleri anlık olarak sunan platform, sizi dünyanın nabzıyla buluşturuyor. Son dakika haberlerini kaçırmamak için gamestity takip edin valorant

Leave a Reply

Your email address will not be published. Required fields are marked *