917. Reverse Only Letters

EasyView on LeetCode

Two Pointers String

Time: O(n)

Space: O(n)

Problem Overview

Reverse only the letters in the string; keep non-letters (digits, punctuation) in place.

Intuition

Reverse only the letters in the string; keep non-letters (digits, punctuation) in place. Two pointers from both ends swap letter pairs after skipping non-letters inward.

Algorithm

1Convert string to char array. Set lo = 0, hi = n - 1.
2While lo < hi: advance lo past non-letters; advance hi past non-letters.
3If lo < hi, swap s[lo] and s[hi]. Increment lo and decrement hi.
4Return new string from char array.

Example Walkthrough

Input: s = "ab-cd"

1.Letters at indices 0,1,3,4 are a,b,c,d. Non-letters: hyphen stays at index 2.
2.Swap a↔d and b↔c around the fixed hyphen → "dc-ba".

Output: "dc-ba"

Common Pitfalls

•Re-check lo < hi after skipping — pointers can cross.
•Only swap when both positions hold letters.
•Strings are immutable in Java — use char[] in place.

917.cs

// Approach: Two-pointer swap; advance left/right pointers past non-letter characters, then swap the bracketing letters.
// Time: O(n) Space: O(n)

public class Solution
{
    public string ReverseOnlyLetters(string s)
    {
        // Convert the input string to a character array for easier manipulation.
        char[] characters = s.ToCharArray();

        // Initialize two pointers.
        int left = 0; // The beginning of the string
        int right = s.Length - 1; // The end of the string

        // Use a while loop to iterate over the character array until the two pointers meet.
        while (left < right)
        {
            // Move the left pointer to the right as long as the current character isn't a letter.
            while (left < right && !char.IsLetter(characters[left]))
                left++;

            // Move the right pointer to the left as long as the current character isn't a letter.
            while (left < right && !char.IsLetter(characters[right]))
                right--;

            // Once both pointers are at letters, swap the characters.
            if (left < right)
            {
                char temp = characters[left];
                characters[left] = characters[right];
                characters[right] = temp;

                // Move both pointers towards the center.
                left++;
                right--;
            }
        }

        // Convert the manipulated character array back to a string and return it.
        return new string(characters);
    }
}

Was this solution helpful?