Leetcode 917. Reverse Only Letters

Problem Explanation

Given a string S, the aim is to reverse only the letters in the string while keeping all the other characters unchanged and at the same place.

Let's take an example to illustrate this. Supposing our string S is "ab-cd". We see that the characters - should remain at the same position, while the letters a, b, c, d, should be reversed. Therefore, the output of this example should be "dc-ba".

We can solve this problem by using a simple two-pointers approach. Initially, we set two pointers: one at the start of the string (i), and another at the end of the string (j). We then start moving those pointers towards each other (i.e., i increases and j decreases) until they meet in the middle.

At each step of the algorithm, we swap the letters at the i-th and j-th position, unless the character is not a letter, in which case we continue moving the pointers without swapping.

Solution

Python

1
2python
3class Solution:
4    def reverseOnlyLetters(self, s: str) -> str:
5        s = list(s)
6        i, j = 0, len(s) - 1
7        while i < j:
8            if not s[i].isalpha():
9                i += 1
10            elif not s[j].isalpha():
11                j -= 1
12            else:
13                s[i], s[j] = s[j], s[i]
14                i += 1
15                j -= 1
16        return "".join(s)

Java

1
2java
3class Solution {
4    public String reverseOnlyLetters(String s) {
5        char[] chars = s.toCharArray();
6        int i = 0, j = s.length() - 1;
7        while (i < j) {
8            if (!Character.isLetter(chars[i])) i++;
9            else if (!Character.isLetter(chars[j])) j--;
10            else {
11                char temp = chars[i];
12                chars[i++] = chars[j];
13                chars[j--] = temp;
14            }
15        }
16        return new String(chars);
17    }
18}

JavaScript

1
2javascript
3var reverseOnlyLetters = function(s) {
4    s = s.split('');
5    let i = 0, j = s.length - 1;
6    while (i < j) {
7        if (!/[a-zA-Z]/.test(s[i])) i++;
8        else if (!/[a-zA-Z]/.test(s[j])) j--;
9        else [s[i++], s[j--]] = [s[j], s[i]];
10    }
11    return s.join('');
12};

C++

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

C#

1
2csharp
3public class Solution {
4    public string ReverseOnlyLetters(string s) {
5        char[] chars = s.ToCharArray();
6        for(int i = 0, j = s.Length - 1; i < j;) {
7            if(!char.IsLetter(chars[i]))
8                i++;
9            else if(!char.IsLetter(chars[j]))
10                j--;
11            else {
12                char tmp = chars[i];
13                chars[i++] = chars[j];
14                chars[j--] = tmp;
15            }
16        }
17        return new string(chars);
18    }
19}

These solutions follow the same general approach, using the programming language's respective syntax and built-in functions. This algorithm works well for strings of any size, although it should be noted that the time complexity scales linearly with the size of the string, resulting in a time complexity of O(n). As such, it is suitable for both small- and large-size strings.

Using the given algorithms, you can easily manipulate a given string S to meet the specified criteria. Whether you work with Python, JavaScript, Java, C++, or C#, you can implement this solution in your preferred language to get the desired result.

This problem is a common type seen in coding interviews, making it a good one to practice with. Understanding its logic can help tackle more complex problems that involve arranging or manipulating strings.

As you implement these solutions, you can gain further insights into how string manipulations work in each of these languages. It can also enhance your familiarity with different condition checks like verifying whether a character is alphabet or not. This specific problem of reversing letters ignoring other characters also tests your understanding of pointers or the equivalent feature in your language of choice. Through practicing and implementing this problem solution, you will be able to enhance these crucial skills. So keep coding, keep learning!


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫