Problem

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.

Examples

Example 1

1
2

Input: s = "ab-cd"
Output: "dc-ba"

Example 2

1
2

Input: s = "a-bC-dEf-ghIj"
Output: "j-Ih-gfE-dCba"

Example 3

1
2

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 '\\'.

Solution

Method 1 - Two Pointers

Intuition

We want to reverse only the letters, keeping all other characters in their original positions. This is a classic two-pointer problem.

Approach

Use two pointers, one at the start and one at the end. Move both pointers towards each other, swapping letters when both point to a letter, and skipping non-letter characters.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#include <string>
using namespace std;
class Solution {
public:
    string reverseOnlyLetters(string s) {
        int l = 0, r = s.size() - 1;
        while (l < r) {
            if (!isalpha(s[l])) l++;
            else if (!isalpha(s[r])) r--;
            else {
                swap(s[l], s[r]);
                l++; r--;
            }
        }
        return s;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func reverseOnlyLetters(s string) string {
    b := []byte(s)
    l, r := 0, len(b)-1
    for l < r {
        if !isLetter(b[l]) {
            l++
        } else if !isLetter(b[r]) {
            r--
        } else {
            b[l], b[r] = b[r], b[l]
            l++
            r--
        }
    }
    return string(b)
}
func isLetter(c byte) bool {
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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

class Solution {
    fun reverseOnlyLetters(s: String): String {
        val arr = s.toCharArray()
        var l = 0
        var r = arr.size - 1
        while (l < r) {
            if (!arr[l].isLetter()) l++
            else if (!arr[r].isLetter()) r--
            else {
                val tmp = arr[l]; arr[l] = arr[r]; arr[r] = tmp
                l++
                r--
            }
        }
        return String(arr)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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

impl Solution {
    pub fn reverse_only_letters(s: String) -> String {
        let mut arr: Vec<char> = s.chars().collect();
        let (mut l, mut r) = (0, arr.len() - 1);
        while l < r {
            if !arr[l].is_ascii_alphabetic() {
                l += 1;
            } else if !arr[r].is_ascii_alphabetic() {
                r -= 1;
            } else {
                arr.swap(l, r);
                l += 1;
                r -= 1;
            }
        }
        arr.into_iter().collect()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

function reverseOnlyLetters(s: string): string {
    const arr = s.split('');
    let l = 0, r = arr.length - 1;
    const isLetter = (c: string) => /[a-zA-Z]/.test(c);
    while (l < r) {
        if (!isLetter(arr[l])) l++;
        else if (!isLetter(arr[r])) r--;
        else {
            [arr[l], arr[r]] = [arr[r], arr[l]];
            l++;
            r--;
        }
    }
    return arr.join('');
}

Complexity

  • ⏰ Time complexity: O(n) — each character is visited at most once.
  • 🧺 Space complexity: O(n) — for the output string/array.