Which ArrayDeque is this, Kotlin's or java.util's?

Without an import, ArrayDeque resolves to kotlin.collections.ArrayDeque, which has addLast, removeLast and removeLastOrNull. If you add import java.util.* you get java.util.ArrayDeque instead, whose push and pop work at the head and whose pop throws NoSuchElementException on an empty deque. Either works; just do not mix the two APIs.

Why removeLastOrNull() instead of removeLast()?

removeLast() throws NoSuchElementException when the deque is empty, which is exactly what a stray closer like the first ) of ")(" produces. removeLastOrNull() returns null there, and null != ch is true, so the method returns false without a separate isEmpty() check.

Can I use a MutableList as the stack?

Yes. mutableListOf () with add and removeLastOrNull() behaves the same and is also amortised O(1) at the end. Note that removeLast() on a MutableList maps to a JDK 21 method on newer JVMs, which is one more reason to prefer removeLastOrNull() or ArrayDeque.

Why does the pair-removal loop copy s into a var?

Function parameters in Kotlin are read-only vals, so s = shorter does not compile. A local var current = s holds the shrinking string; the String itself is immutable, so each replace returns a new one.

Can an odd length be rejected up front?

Yes. Every valid string is made of pairs, so if (s.length % 2 != 0) return false is a safe shortcut before the loop. It does not change the O(n) bound, it only skips the walk for inputs like "(()[]".

Valid Parentheses in Kotlin: Pair Removal and Stack Solutions

is_valid.kt

Kotlin 2.4

Not run yet

+ 7 hidden

Input

s = "{[()()]}"

Expected

true

Each pair closes inside the one that opened before it, and nothing is left open.

1 · Brute force: delete adjacent pairs until nothing changes

2 · One pass with a stack of expected closers

1 · Brute force: delete adjacent pairs until nothing changes

2 · One pass with a stack of expected closers

1 · Brute force: delete adjacent pairs until nothing changes

2 · One pass with a stack of expected closers

1 · Brute force: delete adjacent pairs until nothing changes

2 · One pass with a stack of expected closers

1 · Brute force: delete adjacent pairs until nothing changes

2 · One pass with a stack of expected closers

1 · Brute force: delete adjacent pairs until nothing changes

2 · One pass with a stack of expected closers

1 · Brute force: delete adjacent pairs until nothing changes

2 · One pass with a stack of expected closers

1 · Brute force: delete adjacent pairs until nothing changes

2 · One pass with a stack of expected closers

1 · Brute force: delete adjacent pairs until nothing changes

2 · One pass with a stack of expected closers

1 · Brute force: delete adjacent pairs until nothing changes

2 · One pass with a stack of expected closers

1 · Brute force: delete adjacent pairs until nothing changes

2 · One pass with a stack of expected closers

1 · Brute force: delete adjacent pairs until nothing changes

2 · One pass with a stack of expected closers

1 · Brute force: delete adjacent pairs until nothing changes

2 · One pass with a stack of expected closers

1 · Brute force: delete adjacent pairs until nothing changes

2 · One pass with a stack of expected closers

1 · Brute force: delete adjacent pairs until nothing changes

2 · One pass with a stack of expected closers