Задача: 1190. Reverse Substrings Between Each Pair of Parentheses
Сложность: medium

Дана строка s, состоящая из строчных букв английского алфавита и скобок.

Переверните строки в каждой паре соответствующих скобок, начиная с самой внутренней.

Ваш результат не должен содержать скобок.

Пример:

Input: s = "(abcd)"
Output: "dcba"

👨‍💻 Алгоритм:

1⃣Инициализируйте пустой стек openParenthesesIndices для отслеживания начальных точек разворота и пустую строку result для построения выходного результата.

2⃣Для каждого символа currentChar во входной строке:
Если это '(', добавьте длину строки result в openParenthesesIndices, чтобы отметить потенциальную начальную точку разворота.
Если это ')', извлеките значение из openParenthesesIndices и переверните result от извлеченного индекса для выполнения необходимого разворота.
В противном случае добавьте currentChar к result для построения строки.

3⃣Верните result как окончательную строку со всеми примененными разворотами.

😎 Решение:

class Solution {
    public String reverseParentheses(String s) {
        Stack<Integer> openParenthesesIndices = new Stack<>();
        StringBuilder result = new StringBuilder();

        for (char currentChar : s.toCharArray()) {
            if (currentChar == '(') {
                openParenthesesIndices.push(result.length());
            } else if (currentChar == ')') {
                int start = openParenthesesIndices.pop();
                reverse(result, start, result.length() - 1);
            } else {
                result.append(currentChar);
            }
        }

        return result.toString();
    }

    private void reverse(StringBuilder sb, int start, int end) {
        while (start < end) {
            char temp = sb.charAt(start);
            sb.setCharAt(start++, sb.charAt(end));
            sb.setCharAt(end--, temp);
        }
    }
}

Ставь 👍 и забирай 📚 Базу знаний