1249. Minimum Remove to Make Valid Parentheses

leetcode medium

#csharp#leetcode#medium#stack#string

Task

Дана строка s из '(' , ')' и строчных английских символов. Ваша задача - удалить минимальное количество скобок ( '(' или ')' в любых позициях), чтобы полученная строка со скобками была допустимой, и вернуть любую допустимую строку. Формально строка со скобками допустима тогда и только тогда, когда: она пустая, содержит только строчные символы, или может быть записана как AB (A, конкатенированная с B), где A и B - допустимые строки, или может быть записана как (A), где A - допустимая строка.

Пример:

Input: s = "lee(t(c)o)de)"

Output: "lee(t(c)o)de"

C# solution

matched/original

public class Solution {
    public string MinRemoveToMakeValid(string s) {
        var stack = new Stack<int>();
        var sb = new StringBuilder(s);
        for (int i = 0; i < sb.Length; i++) {
            if (sb[i] == '(') {
                stack.Push(i);
            } else if (sb[i] == ')') {
                if (stack.Count > 0) {
                    stack.Pop();
                } else {
                    sb[i] = '*';
                }
            }
        }
        while (stack.Count > 0) {
            sb[stack.Pop()] = '*';
        }
        return sb.ToString().Replace("*", "");
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public string MinRemoveToMakeValid(string s) {
        var stack = new stack<int>();
        var sb = new StringBuilder(s);
        for (int i = 0; i < sb.size(); i++) {
            if (sb[i] == '(') {
                stack.push(i);
            } else if (sb[i] == ')') {
                if (stack.size() > 0) {
                    stack.pop();
                } else {
                    sb[i] = '*';
                }
            }
        }
        while (stack.size() > 0) {
            sb[stack.pop()] = '*';
        }
        return sb.ToString().Replace("*", "");
    }
}

Java solution

auto-draft, review before submit

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public String MinRemoveToMakeValid(String s) {
        var stack = new Stack<int>();
        var sb = new StringBuilder(s);
        for (int i = 0; i < sb.length; i++) {
            if (sb[i] == '(') {
                stack.push(i);
            } else if (sb[i] == ')') {
                if (stack.size() > 0) {
                    stack.pop();
                } else {
                    sb[i] = '*';
                }
            }
        }
        while (stack.size() > 0) {
            sb[stack.pop()] = '*';
        }
        return sb.ToString().Replace("*", "");
    }
}

JavaScript solution

matched/original

var minRemoveToMakeValid = function(s) {
    let stack = [];
    s = s.split('');
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') {
            stack.push(i);
        } else if (s[i] === ')') {
            if (stack.length) {
                stack.pop();
            } else {
                s[i] = '';
            }
        }
    }
    while (stack.length) {
        s[stack.pop()] = '';
    }
    return s.join('');
};

Go solution

matched/original

func minRemoveToMakeValid(s string) string {
    stack := []int{}
    res := []byte(s)
    for i := 0; i < len(res); i++ {
        if res[i] == '(' {
            stack = append(stack, i)
        } else if res[i] == ')' {
            if len(stack) > 0 {
                stack = stack[:len(stack)-1]
            } else {
                res[i] = '*'
            }
        }
    }
    for len(stack) > 0 {
        res[stack[len(stack)-1]] = '*'
        stack = stack[:len(stack)-1]
    }
    return strings.ReplaceAll(string(res), "*", "")
}

Explanation

Algorithm

Пройдите по строке s и сохраните индексы всех открывающих скобок '(' в стек. При встрече закрывающей скобки ')', удалите соответствующую открытую скобку из стека. Если в стеке нет соответствующей открывающей скобки, пометьте эту закрывающую скобку для удаления.

После первого прохода, все оставшиеся в стеке открывающие скобки пометьте для удаления.

Создайте новую строку, удалив все помеченные скобки.

😎