Reverse Only Letters

easy two pointers string

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, and all the English letters (lowercase or uppercase) should be reversed. Return s after the reversal.

Inputs = "a-bC-dEf-ghIj"

Output"j-Ih-gfE-dCba"

The hyphens stay put; the letters a,b,C,d,E,f,g,h,I,j are reversed to j,I,h,g,f,E,d,C,b,a.

s (string)

def reverse_only_letters(s):
    chars = list(s)
    i, j = 0, len(chars) - 1
    while i < j:
        if not chars[i].isalpha():
            i += 1
        elif not chars[j].isalpha():
            j -= 1
        else:
            chars[i], chars[j] = chars[j], chars[i]
            i += 1
            j -= 1
    return "".join(chars)

function reverseOnlyLetters(s) {
  const chars = s.split("");
  let i = 0, j = chars.length - 1;
  const isAlpha = (c) => /[a-zA-Z]/.test(c);
  while (i < j) {
    if (!isAlpha(chars[i])) i++;
    else if (!isAlpha(chars[j])) j--;
    else {
      [chars[i], chars[j]] = [chars[j], chars[i]];
      i++;
      j--;
    }
  }
  return chars.join("");
}

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

string reverseOnlyLetters(string s) {
    int i = 0, j = (int)s.size() - 1;
    while (i < j) {
        if (!isalpha((unsigned char)s[i])) i++;
        else if (!isalpha((unsigned char)s[j])) j--;
        else {
            swap(s[i], s[j]);
            i++;
            j--;
        }
    }
    return s;
}

Explanation

We want to reverse only the letters while leaving every non-letter (like hyphens) frozen in place. The clean trick is the classic two-pointer swap, but with a twist: we skip over anything that is not a letter.

Pointer i starts at the left and j at the right. If chars[i] is not a letter, we just move i forward. If chars[j] is not a letter, we move j backward. Those non-letters never move, exactly as required.

Only when both i and j point at real letters do we swap them, then step both pointers inward. We continue until the pointers meet, at which point all the letters have been mirrored.

Because each character is looked at a constant number of times, this is a single linear-time pass.

Example: s = "a-bC-dEf". The letters are a, b, C, d, E, f; the hyphens stay put. Reversing just the letters to f, E, d, C, b, a and dropping them back into the non-hyphen slots gives "f-Ed-Cba".

Time: O(n) Space: O(n)