Reverse Only Letters

Easy
509.

Reverse Only Letters

Reverse Only Letters is an easy coding problem on strings and two pointers, asked in Amazon and Adobe interviews.

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 <= 100
  • s consists of ASCII characters and contains no backslash or double quote.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {string}
 */
var reverseOnlyLetters = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 100
  • s consists of ASCII characters and contains no backslash or double quote.

Hints for Reverse Only Letters

  1. Hint 1

    Two pointers, one at each end, is the natural fit.

  2. Hint 2

    Advance a pointer past any non-letter without swapping.

  3. 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

  1. Convert the string to a mutable character array.
  2. Place i at the start and j at the end.
  3. If s[i] is not a letter, advance i; if s[j] is not a letter, retreat j.
  4. When both are letters, swap them and move both pointers inward.
  5. Stop when i >= j and 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-z and A-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