Scale Engineer

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
SnowflakeZohoTuring

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.

class Solution {    public String reverseOnlyLetters(String s) {        StringBuilder letters = new StringBuilder();        for (char c : s.toCharArray()) {            if (Character.isLetter(c)) {                letters.append(c);            }        }        letters.reverse();                StringBuilder result = new StringBuilder();        int letterIndex = 0;        for (char c : s.toCharArray()) {            if (Character.isLetter(c)) {                result.append(letters.charAt(letterIndex));                letterIndex++;            } else {                result.append(c);            }        }                return result.toString();    }}

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.

Solutions

class Solution {public  String reverseOnlyLetters(String s) {    char[] chars = s.toCharArray();    int i = 0, j = s.length() - 1;    while (i < j) {      while (i < j && !Character.isLetter(chars[i])) {        ++i;      }      while (i < j && !Character.isLetter(chars[j])) {        --j;      }      if (i < j) {        char t = chars[i];        chars[i] = chars[j];        chars[j] = t;        ++i;        --j;      }    }    return new String(chars);  }}

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 →

Next problem