Reverse Only Letters solution and explanation
Google
9 more videos on this problem
LeetCode Reverse Only Letters Solution Explained - JavaNick White · 7:35 · 11K views
Reverse only letters | Leetcode 917Technosage · 7:47 · 6K views
Reverse Only Letters (LeetCode 917) | 2 Different Methods | Stack Data Structure and Two PointersNikhil Lohia · 13:07 · 3K views
Leetcode - Reverse Only Letters (Python)Timothy H Chang · 2:42 · 2K views
Reverse Only Letters | Leetcode 917 | Live coding session 🔥🔥🔥Coding Decoded · 6:02 · 1K views
LeetCode 917 : Reverse Only Letters || EASY || C++ || JAVA || Detailed SolutionCodeGPT · 10:18 · 416 views
Leetcode 917 - Reverse Only Letters (JAVA, Solution Explain!)LC Bear · 4:43 · 321 views
Reverse Only Letters LeetCode 917 | Two Pointers | JavaScriptSantamaria Code · 6:33 · 283 views
LeetCode 917 Reverse Only LettersFAANG Interviews · 6:19 · 258 views
Daily Leetcode #532: Sep 14, 2021 - 917. Reverse Only LettersProgramming Live with Larry · 5:26 · 223 views
The problem
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.
class Solution:
def reverseOnlyLetters(self, s: str) -> str:
s = list(s)
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalpha():
left += 1
while left < right and not s[right].isalpha():
right -= 1
if left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
return ''.join(s)
# Example usage
sol = Solution()
print(sol.reverseOnlyLetters("a-bC-dEf-ghIj"))class Solution {
public String reverseOnlyLetters(String s) {
char[] arr = s.toCharArray();
int left = 0, right = arr.length - 1;
while (left < right) {
while (left < right && !Character.isLetter(arr[left])) left++;
while (left < right && !Character.isLetter(arr[right])) right--;
if (left < right) {
char temp = arr[left];
arr[left++] = arr[right];
arr[right--] = temp;
}
}
return new String(arr);
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.reverseOnlyLetters("a-bC-dEf-ghIj"));
}
}#include <iostream>
#include <cctype>
std::string reverseOnlyLetters(std::string s) {
int left = 0, right = s.length() - 1;
while (left < right) {
while (left < right && !isalpha(s[left])) left++;
while (left < right && !isalpha(s[right])) right--;
if (left < right) std::swap(s[left++], s[right--]);
}
return s;
}
int main() {
std::string s = "a-bC-dEf-ghIj";
std::cout << reverseOnlyLetters(s) << std::endl;
return 0;
}function reverseOnlyLetters(S) {
const arr = S.split('');
let left = 0, right = arr.length - 1;
while (left < right) {
while (left < right && !(/[a-zA-Z]/).test(arr[left])) left++;
while (left < right && !(/[a-zA-Z]/).test(arr[right])) right--;
if (left < right) {
[arr[left], arr[right]] = [arr[right], arr[left]];
left++;
right--;
}
}
return arr.join('');
}
console.log(reverseOnlyLetters("a-bC-dEf-ghIj"));#include <stdio.h>
#include <ctype.h>
#include <string.h>
char* reverseOnlyLetters(char* s) {
int left = 0, right = strlen(s) - 1;
while (left < right) {
while (left < right && !isalpha(s[left])) {
left++;
}
while (left < right && !isalpha(s[right])) {
right--;
}
if (left < right) {
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
}
return s;
}
int main() {
char str[] = "a-bC-dEf-ghIj";
printf("%s\n", reverseOnlyLetters(str));
return 0;
}using System;
class Solution {
public string ReverseOnlyLetters(string s) {
char[] arr = s.ToCharArray();
int left = 0, right = s.Length - 1;
while (left < right) {
while (left < right && !char.IsLetter(arr[left])) left++;
while (left < right && !char.IsLetter(arr[right])) right--;
if (left < right) {
char temp = arr[left];
arr[left++] = arr[right];
arr[right--] = temp;
}
}
return new string(arr);
}
static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.ReverseOnlyLetters("a-bC-dEf-ghIj"));
}
}This Python solution utilizes the isalpha() method of string objects to determine if a character is a letter. Two pointers are employed to toggle positions of the letters.
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n), as the string is converted to a list for in-place modifications.
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.
class Solution:
def reverseOnlyLetters(self, s: str) -> str:
letters = [c for c in s if c.isalpha()]
result = []
for c in s:
if c.isalpha():
result.append(letters.pop())
else:
result.append(c)
return ''.join(result)
# Example usage
sol = Solution()
print(sol.reverseOnlyLetters("a-bC-dEf-ghIj"))import java.util.Stack;
class Solution {
public String reverseOnlyLetters(String s) {
Stack<Character> letters = new Stack<>();
for (char c : s.toCharArray()) {
if (Character.isLetter(c)) letters.push(c);
}
StringBuilder result = new StringBuilder();
for (char c : s.toCharArray()) {
if (Character.isLetter(c)) {
result.append(letters.pop());
} else {
result.append(c);
}
}
return result.toString();
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.reverseOnlyLetters("a-bC-dEf-ghIj"));
}
}#include <iostream>
#include <stack>
#include <cctype>
std::string reverseOnlyLetters(std::string s) {
std::stack<char> letters;
for (char c : s) {
if (isalpha(c)) letters.push(c);
}
for (char &c : s) {
if (isalpha(c)) {
c = letters.top();
letters.pop();
}
}
return s;
}
int main() {
std::string s = "a-bC-dEf-ghIj";
std::cout << reverseOnlyLetters(s) << std::endl;
return 0;
}function reverseOnlyLetters(S) {
const stack = [];
for (const char of S) {
if (/[a-zA-Z]/.test(char)) {
stack.push(char);
}
}
let result = '';
for (const char of S) {
if (/[a-zA-Z]/.test(char)) {
result += stack.pop();
} else {
result += char;
}
}
return result;
}
console.log(reverseOnlyLetters("a-bC-dEf-ghIj"));#include <stdio.h>
#include <ctype.h>
#include <string.h>
char* reverseOnlyLetters(char* s) {
int stack[100], top = -1;
int len = strlen(s);
for (int i = 0; i < len; i++) {
if (isalpha(s[i])) {
top++;
stack[top] = s[i];
}
}
for (int i = 0; i < len; i++) {
if (isalpha(s[i])) {
s[i] = stack[top];
top--;
}
}
return s;
}
int main() {
char str[] = "a-bC-dEf-ghIj";
printf("%s\n", reverseOnlyLetters(str));
return 0;
}using System;
using System.Collections.Generic;
class Solution {
public string ReverseOnlyLetters(string s) {
Stack<char> letters = new Stack<char>();
foreach (char c in s) {
if (char.IsLetter(c)) {
letters.Push(c);
}
}
char[] result = new char[s.Length];
for (int i = 0; i < s.Length; i++) {
if (char.IsLetter(s[i])) {
result[i] = letters.Pop();
} else {
result[i] = s[i];
}
}
return new string(result);
}
static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.ReverseOnlyLetters("a-bC-dEf-ghIj"));
}
}The Python solution uses a list comprehension to collect letters and pop() to reverse their order when building the final result.
Time Complexity: O(n), since each letter is examined twice.
Space Complexity: O(n), due to the temporary storage for letters.
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.
function reverseOnlyLetters(s: string): string {
const cs = [...s];
let [i, j] = [0, cs.length - 1];
while (i < j) {
while (!/[a-zA-Z]/.test(cs[i]) && i < j) {
i++;
}
while (!/[a-zA-Z]/.test(cs[j]) && i < j) {
j--;
}
[cs[i], cs[j]] = [cs[j], cs[i]];
i++;
j--;
}
return cs.join('');
}func reverseOnlyLetters(s string) string {
cs := []rune(s)
i, j := 0, len(s)-1
for i < j {
for i < j && !unicode.IsLetter(cs[i]) {
i++
}
for i < j && !unicode.IsLetter(cs[j]) {
j--
}
if i < j {
cs[i], cs[j] = cs[j], cs[i]
i++
j--
}
}
return string(cs)
}impl Solution {
pub fn reverse_only_letters(s: String) -> String {
let mut cs: Vec<char> = s.chars().collect();
let n = cs.len();
let mut l = 0;
let mut r = n - 1;
while l < r {
if !cs[l].is_ascii_alphabetic() {
l += 1;
} else if !cs[r].is_ascii_alphabetic() {
r -= 1;
} else {
cs.swap(l, r);
l += 1;
r -= 1;
}
}
cs.iter().collect()
}
}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), since each letter is examined twice. |
| Two Pointers | – |
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 |
Frequently asked questions
Is Reverse Only Letters easy or hard?
Reverse Only Letters is classified as an Easy problem. It mainly tests understanding of string traversal and the two pointer pattern, which makes it a common early interview or practice problem.
Reverse Only Letters Python/Java solution
In Python or Java, convert the string into a mutable character array and apply the two pointer technique. Move pointers inward while skipping non-letter characters and swap letters when found. The implementation runs in O(n) time and uses constant extra space.
How to solve Reverse Only Letters in O(n)?
Use the two pointer technique. Convert the string to a character array, place one pointer at the start and another at the end, and skip any characters that are not alphabetic. When both pointers point to letters, swap them and continue until the pointers cross. This guarantees a single linear pass.
What is the best approach for Reverse Only Letters?
The two pointer approach is the best solution. Start one pointer at the beginning and another at the end of the string, skipping non-letter characters and swapping letters when both pointers land on alphabetic characters. This processes the string in O(n) time and uses O(1) extra space.
Is Reverse Only Letters asked at Google/Amazon/Meta?
Problems involving string manipulation with two pointers appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact question may vary, the pattern of skipping characters and reversing selected elements is a common interview theme.
What data structure is used in Reverse Only Letters?
The optimal method primarily uses the two pointer technique on a character array. An alternative implementation uses a stack to store letters and reconstruct the string in reverse order while leaving non-letter characters unchanged.
What is the time complexity of Reverse Only Letters?
The optimal solution runs in O(n) time because each character is examined at most once while the two pointers move toward the center. A stack-based implementation also runs in O(n) time but requires O(n) additional memory to store letters.