Skip to interview prep
Apexed

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.

A string has the form `w X reverse(w)` with a single marker X in the middle. How can a stack verify it — Data structures & algorithms interview question — Apexe