Reverse Only Letters - Solution & Explanation
Problem Statement
Given a string s, reverse the string according to the following rules:
- All the characters that are not English letters remain in the same position.
- All the English letters (lowercase or uppercase) should be reversed.
Return s after reversing it.
Example 1:
Input: s = "ab-cd" Output: "dc-ba"
Example 2:
Input: s = "a-bC-dEf-ghIj" Output: "j-Ih-gfE-dCba"
Example 3:
Input: s = "Test1ng-Leet=code-Q!" Output: "Qedo1ct-eeLg=ntse-T!"
Constraints:
1 <= s.length <= 100sconsists of characters with ASCII values in the range[33, 122].sdoes not contain'\"'or'\\'.
Approach Overview
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.
Approach 1: Two Pointer Approach
Using a two-pointer technique, we can efficiently reverse only the letters in the string. One pointer starts from the beginning and the other from the end. We swap letters when both pointers are on valid letters. If a pointer is on a non-letter, it moves until it finds a letter. The process continues until the two pointers meet or cross each other.
This C function uses two pointers to reverse letters in a string. The isalpha() function checks for letters, and strlen() gives the length to set the right pointer. A simple swap operation is done when both pointers point to letters.
Complexity
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(1), as we are modifying the string in place.
Approach 2: Stack-Based Approach
This approach uses a stack to collect all the letters in the string and then reinserts them in reverse order while iterating through the original string.
C solution employs a manual stack using an array to reverse letters. The letters are first pushed into the stack and then popped off when reinserting into the original string.
Complexity
Time Complexity: O(n), for iterating through the string twice.
Space Complexity: O(n), for storing letter characters in the stack.
Approach 3: Two Pointers
We use two pointers i and j to point to the head and tail of the string respectively. When i < j, we continuously move i and j until i points to an English letter and j points to an English letter, then we swap s[i] and s[j]. Finally, we return the string.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the string.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Two Pointer Approach | Time Complexity: O(n), where n is the length of the string. |
| Stack-Based Approach | Time Complexity: O(n), for iterating through the string twice. |
| Two Pointers | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pointer Approach | O(n) | O(1) | Best general solution when you want optimal time and constant memory |
| Stack-Based Approach | O(n) | O(n) | Useful when separating reversal logic from traversal or when teaching stack behavior |
Video Solution
LeetCode Reverse Only Letters Solution Explained - Java • Nick White • 11,368 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Reverse Only Letters easy or hard?
Reverse Only Letters Python/Java solution
How to solve Reverse Only Letters in O(n)?
What is the best approach for Reverse Only Letters?
Is Reverse Only Letters asked at Google/Amazon/Meta?
What data structure is used in Reverse Only Letters?
What is the time complexity of Reverse Only Letters?
Ready to solve this problem?
Practice Reverse Only Letters with our built-in code editor and test cases.
Practice on FleetCode