Reverse Only Letters - Solution & Explanation

Problem Overview: You receive a string containing letters and non-letter characters such as digits, hyphens, or punctuation. The task is to reverse only the alphabetic characters while keeping every non-letter character in its original index. For example, in a-bC-dEf-ghIj, the letters reverse order but hyphens remain fixed.

Approach 1: Two Pointer Approach (O(n) time, O(1) space)

This is the most efficient and commonly expected solution. Use two pointers: one starting at the beginning of the string and one at the end. Move both pointers inward. If the left pointer points to a non-letter, move it forward. If the right pointer points to a non-letter, move it backward. When both pointers land on alphabetic characters, swap them and continue moving inward.

The key insight is that only letters participate in the reversal, while other characters simply act as fixed boundaries. You only scan the string once, so the runtime is O(n). Because swaps happen directly inside a character array and no extra data structures are needed, the space complexity stays O(1). This approach is a classic application of Two Pointers applied to a String.

This method performs well even for large inputs because each character is visited at most once by each pointer. It is also easy to implement in languages where strings can be converted to mutable arrays.

Approach 2: Stack-Based Approach (O(n) time, O(n) space)

The stack approach separates the reversal logic from the traversal. First iterate through the string and push every alphabetic character onto a stack. This effectively stores the letters in reverse order because stacks follow Last-In-First-Out behavior.

Next iterate through the string again. When you encounter a letter, pop the top element from the stack and place it into the current position. When you encounter a non-letter character, copy it directly to the result without modification. Because each letter is pushed and popped once, the total runtime remains O(n).

The tradeoff is extra memory. The stack stores up to all letters in the string, giving O(n) space complexity. This approach can feel simpler conceptually because the reversal is handled automatically by the stack, but it uses more memory than necessary. It demonstrates how a Stack can help when reversing sequences.

Recommended for interviews: The two pointer technique is the expected answer in most interviews. It shows that you can reason about in-place transformations and efficiently skip irrelevant characters. The stack solution still demonstrates solid understanding and is useful as a stepping stone, but interviewers usually prefer the constant-space two pointer implementation.