Reverse Only Letters

Easy Arrays & Hashing Two Pointer Original on LeetCode

Reported atZohoShareChat

Reverse Only Letters is a easy arrays & hashing problem solved with the two pointer pattern. The best approach, optimal (two pointers, in place), runs in O(n) time and O(n) for the char array (O(1) extra) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (collect the letters, then refill) up.

Problem

Given a string s, reverse the order of its English letters (a-z and A-Z) while every other character stays exactly where it is. Return the resulting string.

Examples

Example 1

Input
s = "x-yz"
Output
"z-yx"
Why
The letters x, y, z are reversed; the dash stays at index 1.

Example 2

Input
s = "Go4-it!"
Output
"ti4-oG!"
Why
Only G, o, i, t move. The characters 4, - and ! keep their positions.

Constraints

  • 1 <= s.length <= 100
  • s consists of printable ASCII characters with codes from 33 to 122.
  • s does not contain a double quote or a backslash.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (collect the letters, then refill)O(n)O(n)
Optimal (two pointers, in place)O(n)O(n) for the char array (O(1) extra)

1Brute force (collect the letters, then refill)

TimeO(n)Two passes over the string.
SpaceO(n)The stack can hold every letter.

Push every letter onto a stack. Then build the answer from left to right: copy non-letters as they are, and for each letter position pop the next letter from the stack, which hands the letters back in reverse order.

  1. Push every letter of s onto a stack.
  2. For each character c of s: append c if it is not a letter, otherwise append stack.pop().
  3. Return the built string.
class Solution {
    public String reverseOnlyLetters(String s) {
        Deque<Character> st = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (Character.isLetter(c)) st.push(c);
        }
        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) {
            sb.append(Character.isLetter(c) ? st.pop() : c);
        }
        return sb.toString();
    }
}

2Optimal (two pointers, in place)

TimeO(n)Each step moves at least one pointer inward.
SpaceO(n) for the char array (O(1) extra)Only the mutable copy of the string, which the result needs anyway.

Work on a character array with i at the start and j at the end. Move i right past non-letters and j left past non-letters. When both point at letters, swap them and step both inward. Non-letters are never touched.

  1. i = 0, j = n - 1.
  2. While i < j: if s[i] is not a letter, i++; else if s[j] is not a letter, j--; else swap s[i] and s[j], i++, j--.
  3. Return the array as a string.
class Solution {
    public 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 tmp = a[i];
                a[i++] = a[j];
                a[j--] = tmp;
            }
        }
        return new String(a);
    }
}

Edge cases to test

  • No letters at all: the string is returned unchanged
  • Only letters: plain reversal
  • Upper- and lowercase letters mixed; case is kept with each letter
  • Non-letters at the very start or end

Hints

Hint 1

Non-letters are fixed in place; only the sequence of letters is reversed.

Hint 2

Use two pointers from both ends. Skip non-letters on each side, then swap the two letters and move inward.

FAQ

What is the best time complexity for Reverse Only Letters?

Optimal (two pointers, in place) runs in O(n) time and O(n) for the char array (O(1) extra) extra space. Each step moves at least one pointer inward.

Which pattern does Reverse Only Letters use?

It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.

Is there a brute force solution for Reverse Only Letters?

Yes. Brute force (collect the letters, then refill) takes O(n) time and O(n) space. Push every letter onto a stack.

Which edge cases should I test for Reverse Only Letters?

No letters at all: the string is returned unchanged; Only letters: plain reversal; Upper- and lowercase letters mixed; case is kept with each letter; Non-letters at the very start or end.