Reverse Only Letters

Easy

#0871Time: O(N), where N is the length of the string. We perform two separate passes over the string, and reversing the list of letters takes time proportional to the number of letters (L). The total time is O(N) + O(L) + O(N), which simplifies to O(N) as L <= N.Space: O(N), where N is the length of the string. We need extra space to store the collected letters, which can be up to N in the worst case. We also need space for the result `StringBuilder`, which is also O(N). Thus, the total auxiliary space is O(N).3 companies

Patterns

Two Pointers

Data structures

String

Companies

Snowflake Zoho Turing

Prompt

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 <= 100
s consists of characters with ASCII values in the range [33, 122].
s does not contain '\"' or '\\'.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves three main steps. First, we iterate through the input string to extract all the English letters and store them in a separate data structure, like a list or a StringBuilder. Second, we reverse this collection of letters. Finally, we build a new string by iterating through the original string one more time. If a character is a letter, we append the next letter from our reversed collection; otherwise, we append the non-letter character as is.

Algorithm

Create a StringBuilder or a list to store only the letters from the input string s.
Iterate through s. For each character, check if it's an English letter using Character.isLetter().
If it is a letter, append it to the StringBuilder/list.
After the first pass, reverse the StringBuilder/list of letters.
Create a new StringBuilder for the final result.
Initialize a pointer/index for the reversed letters list to 0.
Iterate through the original string s again. For each character:
If the character is a letter, append the character from the reversed letters list at the current pointer, and increment the pointer.
If the character is not a letter, append it directly to the result.
Convert the result StringBuilder to a string and return it.

Walkthrough

The core idea is to separate the letters from the non-letters. We can make one pass through the string to collect all the letters into an auxiliary data structure. Once collected, we can easily reverse this collection. Then, we make a second pass through the original string to construct our final answer. When we encounter a position that originally held a letter, we take the next available letter from our reversed collection. When we encounter a non-letter, we place it back in its original position.

1class Solution {2    public String reverseOnlyLetters(String s) {3        StringBuilder letters = new StringBuilder();4        for (char c : s.toCharArray()) {5            if (Character.isLetter(c)) {6                letters.append(c);7            }8        }9        letters.reverse();10        11        StringBuilder result = new StringBuilder();12        int letterIndex = 0;13        for (char c : s.toCharArray()) {14            if (Character.isLetter(c)) {15                result.append(letters.charAt(letterIndex));16                letterIndex++;17            } else {18                result.append(c);19            }20        }21        22        return result.toString();23    }24}

Complexity

Time

O(N), where N is the length of the string. We perform two separate passes over the string, and reversing the list of letters takes time proportional to the number of letters (L). The total time is O(N) + O(L) + O(N), which simplifies to O(N) as L <= N.

Space

O(N), where N is the length of the string. We need extra space to store the collected letters, which can be up to N in the worst case. We also need space for the result `StringBuilder`, which is also O(N). Thus, the total auxiliary space is O(N).

Trade-offs

Pros

Conceptually straightforward and easy to implement.
Separates the logic of finding letters and placing them, which can be easier to debug.

Cons

Requires extra space proportional to the number of letters in the string.
Requires two passes over the input string, which is less efficient than a single-pass solution.

A more efficient approach uses two pointers, one starting from the beginning of the string (left) and the other from the end (right). The pointers move towards each other, skipping over any non-letter characters. When both pointers have found a letter, the characters at these two positions are swapped. This process continues until the pointers meet or cross, effectively reversing the letters in a single pass while leaving non-letter characters untouched.

Algorithm

Convert the input string s into a character array chars to allow for in-place modification.
Initialize two pointers: left = 0 and right = chars.length - 1.
Start a loop that continues as long as left < right.
Inside the loop, move the left pointer forward until it points to a letter (while (left < right && !Character.isLetter(chars[left])) { left++; }).
Similarly, move the right pointer backward until it points to a letter (while (left < right && !Character.isLetter(chars[right])) { right--; }).
Once both pointers are at letters, swap the characters at chars[left] and chars[right].
After the swap, move both pointers towards the center: left++ and right--.
After the loop finishes, convert the modified character array chars back into a string and return it.

Walkthrough

This method is a classic in-place reversal technique adapted for this specific problem. By converting the string to a character array, we can modify it directly. The left pointer seeks the first letter from the start, and the right pointer seeks the first letter from the end. Once found, they are swapped. This ensures that the first letter is swapped with the last, the second with the second-to-last, and so on, achieving the reversal. Non-letters are simply skipped over by the pointers, so they remain in their original positions.

1class Solution {2    public String reverseOnlyLetters(String s) {3        char[] chars = s.toCharArray();4        int left = 0;5        int right = s.length() - 1;6        7        while (left < right) {8            // Find the next letter from the left9            while (left < right && !Character.isLetter(chars[left])) {10                left++;11            }12            13            // Find the next letter from the right14            while (left < right && !Character.isLetter(chars[right])) {15                right--;16            }17            18            // Swap the letters19            if (left < right) {20                char temp = chars[left];21                chars[left] = chars[right];22                chars[right] = temp;23                24                // Move pointers25                left++;26                right--;27            }28        }29        30        return new String(chars);31    }32}

Complexity

Time

O(N), where N is the length of the string. Each pointer, `left` and `right`, traverses the array at most once. Therefore, the total number of operations is proportional to N.

Space

O(N). Although the swap is done 'in-place' on the character array, creating this array from the immutable input string requires O(N) space. This is still an improvement over the first approach which required O(N) for the letters list in addition to O(N) for the result.

Trade-offs

Pros

More space-efficient as it avoids creating a separate list for letters.
Performs the reversal in a single pass over the string.

Cons

The logic of moving two pointers and swapping can be slightly more complex to grasp initially compared to the collect-and-rebuild method.

Solutions

Solution

1class Solution {2public3  String reverseOnlyLetters(String s) {4    char[] chars = s.toCharArray();5    int i = 0, j = s.length() - 1;6    while (i < j) {7      while (i < j && !Character.isLetter(chars[i])) {8        ++i;9      }10      while (i < j && !Character.isLetter(chars[j])) {11        --j;12      }13      if (i < j) {14        char t = chars[i];15        chars[i] = chars[j];16        chars[j] = t;17        ++i;18        --j;19      }20    }21    return new String(chars);22  }23}

1class Solution {2public:3  string reverseOnlyLetters(string s) {4    int i = 0, j = s.size() - 1;5    while (i < j) {6      while (i < j && !isalpha(s[i]))7        ++i;8      while (i < j && !isalpha(s[j]))9        --j;10      if (i < j) {11        swap(s[i], s[j]);12        ++i;13        --j;14      }15    }16    return s;17  }18};

1class Solution:2    def reverseOnlyLetters(self, s: str) -> str: s = list(s) i, j = 0, len(s) - 1 while i < j: while i < j and not s[i]. isalpha(): i += 1 while i < j and not s[j]. isalpha(): j -= 1 if i < j: s[i], s[j] = s[j], s[i] i, j = i + 1, j - 1 return '' . join(s)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem