123. A string has the form `w X reverse(w)` with a single marker X in the middle. How can a stack verify it?
EasyStacks
Technical
Show model answer
Push characters until you reach the marker X. After the marker, pop one character for each remaining input character and compare; any mismatch, an empty stack too early, or leftover characters at the end means the string is not of that form.
This takes O(n) time and O(n) space. With random access you could instead compare from both ends with two indices in O(1) space, but the stack version is the model answer when the input can only be read once, left to right.