Reverse Only Letters — Solution in Python, Java & C++
Reverse Only Letters solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Reverse Only Letters is an easy coding problem on strings and two pointers, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Strings, Two Pointers
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a string s, reverse the order of the English letters in it while leaving every non-letter character at its original index.
Return the resulting string.
Example 1
Input: s = "ab-cd"
Output: dc-ba
Explanation: The dash stays at index 2; the letters a,b,c,d reverse to d,c,b,a.
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 <= 100s consists of ASCII characters and contains no backslash or double quote.
Hints for Reverse Only Letters
Hint 1
Two pointers, one at each end, is the natural fit.
Hint 2
Advance a pointer past any non-letter without swapping.
Hint 3
Swap only when both pointers sit on letters.
How to solve Reverse Only Letters
Non-letters are fixed points: the letters must reverse among themselves, which is exactly what a two-pointer swap does when it skips over everything else.
Approach
- Convert the string to a mutable character array.
- Place
iat the start andjat the end. - If
s[i]is not a letter, advancei; ifs[j]is not a letter, retreatj. - When both are letters, swap them and move both pointers inward.
- Stop when
i >= jand join the array.
Why it works
Each swap pairs the k-th letter from the left with the k-th from the right, which is precisely a reversal of the letter subsequence; skipped positions are never written, so non-letters keep their indices.
Complexity
- Time —
O(n) - Space —
O(n) for the character array
Pitfalls
- Advancing both pointers on every iteration mis-pairs the letters when non-letters are unevenly distributed.
- The letter test must accept both cases —
a-zandA-Z. - Reversing the whole string and then re-inserting non-letters is far more fiddly and easy to get wrong.
Reference solution
Python
def reverseOnlyLetters(s: str) -> str:
a = list(s)
i, j = 0, len(a) - 1
while i < j:
if not a[i].isalpha():
i += 1
elif not a[j].isalpha():
j -= 1
else:
a[i], a[j] = a[j], a[i]
i += 1
j -= 1
return ''.join(a)Java
public static String reverseOnlyLetters(String s) {
char[] a = s.toCharArray();
int i = 0, j = a.length - 1;
while (i < j) {
if (!Character.isLetter(a[i])) i++;
else if (!Character.isLetter(a[j])) j--;
else {
char t = a[i];
a[i] = a[j];
a[j] = t;
i++;
j--;
}
}
return new String(a);
}C++
bool isLetterROL(char c) {
return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
}
string reverseOnlyLetters(string s) {
int i = 0, j = (int) s.size() - 1;
while (i < j) {
if (!isLetterROL(s[i])) i++;
else if (!isLetterROL(s[j])) j--;
else {
char t = s[i];
s[i] = s[j];
s[j] = t;
i++;
j--;
}
}
return s;
}JavaScript
var reverseOnlyLetters = function(s) {
function isLetter(c) {
return (c >= "a" && c <= "z") || (c >= "A" && c <= "Z");
}
const a = s.split("");
let i = 0, j = a.length - 1;
while (i < j) {
if (!isLetter(a[i])) i++;
else if (!isLetter(a[j])) j--;
else {
const t = a[i];
a[i] = a[j];
a[j] = t;
i++;
j--;
}
}
return a.join("");
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Two Pointers Technique