Блог

Например: у нас есть последовательность «(()(()))», тогда ответ равен 0 (ну, это сбалансированная последовательность скобок).

Допустим, у нас есть такая последовательность: «)) (((«, тогда оптимальное число для удаления будет равно 5 (нет другого способа сделать его сбалансированным, кроме удаления их всех)

Если у нас есть такая последовательность: «())(()», тогда ответом будет 2 (давайте удалим третий и четвертый).

вот одно из возможных решений:

1. начните с начала с переменной count = 0 , которая подсчитывает «открытые» скобки и needed = 0 количество скобок, которые вам нужно сбалансировать
2. каждый раз, когда вы находите ( добавить 1 к count
3. каждый раз, когда вы находите ) :
   если count == 0 тогда вам нужны открытые скобки раньше, поэтому вы делаете needed = needed = 1 что-то еще, уменьшайте количество найденных открытых скобок count = count - 1;
4. в конце добавьте количество оставшихся открытых скобок к необходимому, потому что вам нужны count заключительные закрывающие скобки: needed = needed count

в конце:

 count(string)
    count = needed = 0
    for i = 0 to string.length
        if string[i] == '('
            count = count   1
        else if string[i] == ')'
            if count == 0
                 needed = needed   1
            else 
               count = count - 1
    return count   needed
 
  

Вы можете поместить открытые символы в стек, и когда вы столкнетесь с закрытым символом, если стек не пуст, извлеките элемент из стека, если он сбалансирован, иначе увеличьте количество. После итерации добавьте оставшиеся символы, присутствующие в стеке.

 private static int getCount(String input) {
    char open = '(';
    int charsToDelete = 0;
    Stack<Character> characterStack = new Stack<>();
    for (int i=0;i<input.length();i  ) {
        char ch = input.charAt(i);
        if (ch == open) {
            characterStack.push(ch);
        } else {
            if (!characterStack.isEmpty()) {
                char pop = characterStack.peek();
                if (pop == '(') {
                    characterStack.pop();
                } else {
                    charsToDelete  ;
                }
            } else {
                charsToDelete  ;
            }
        }
    }
    while (!characterStack.isEmpty()) {
        characterStack.pop();
        charsToDelete  ;
    }
    return charsToDelete;
}