LeetCode 917 - Reverse Only Letters
The problem asks us to reverse only the English letters in a string while keeping all non-letter characters fixed in their original positions. In other words, letters move, but symbols, digits, and punctuation marks stay exactly where they started.
Difficulty: 🟢 Easy
Topics: Two Pointers, String
Solution
Problem Understanding
The problem asks us to reverse only the English letters in a string while keeping all non-letter characters fixed in their original positions. In other words, letters move, but symbols, digits, and punctuation marks stay exactly where they started.
For example, consider the string "ab-cd". The letters are "a", "b", "c", and "d". Reversing only the letters gives "d", "c", "b", "a". The hyphen remains at index 2, so the final result becomes "dc-ba".
The input is a single string s, and the output is another string of the same length after applying this transformation. The problem guarantees that the string length is between 1 and 100, so the input size is very small. Even though the constraints are small enough that multiple solutions would work efficiently, the goal is still to design a clean and optimal approach.
The characters in the string fall within ASCII values [33, 122], meaning the string may contain uppercase letters, lowercase letters, digits, punctuation, and symbols. Only alphabetic English letters should participate in the reversal.
Several edge cases are important to recognize upfront. A string containing no letters at all should remain unchanged because there is nothing to reverse. A string containing only letters should behave like a normal full-string reversal. Mixed-case letters must preserve their exact characters during reversal, meaning uppercase stays uppercase and lowercase stays lowercase because we are moving characters, not transforming them. Consecutive symbols or digits can also create bugs if pointer movement is not handled carefully.
Approaches
A straightforward brute-force approach is to first extract all letters from the string into a separate list, reverse that list, and then rebuild the string by replacing letter positions with characters from the reversed list. Non-letter characters are copied directly into the result.
This works because the extracted list contains exactly the letters that need to be reversed. During reconstruction, each letter position receives the next character from the reversed sequence, while non-letter characters stay untouched.
Although this approach is perfectly acceptable for the given constraints, it requires extra passes over the string and additional storage proportional to the number of letters. We can do better conceptually by reversing the letters in place using the two-pointer technique.
The key insight is that only letters should move, and all non-letter characters should remain fixed. This naturally suggests using one pointer from the left side and another pointer from the right side. Whenever both pointers point to letters, we swap them and move inward. If either pointer lands on a non-letter character, we skip it because its position must remain unchanged.
This approach avoids explicitly storing the reversed letters separately. Instead, it directly swaps matching letters from opposite ends of the string.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n) | O(n) | Extract letters, reverse them, rebuild string |
| Optimal | O(n) | O(n) | Two pointers swap letters while skipping symbols |
Even though the optimal approach still uses O(n) space in Python and Go because strings are immutable and must be converted into mutable arrays, it avoids storing a separate reversed-letter collection.
Algorithm Walkthrough
- Convert the input string into a mutable character array.
Strings are immutable in both Python and Go, so we cannot swap characters directly inside the original string. Converting the string into a list or byte slice allows in-place modifications. 2. Initialize two pointers.
The left pointer starts at the beginning of the array, and the right pointer starts at the end. These pointers will move toward each other while searching for letters to swap. 3. Move the left pointer until it reaches a letter.
If the current character is not an English letter, it must remain fixed in its original position. Therefore, we skip it and continue moving the left pointer forward. 4. Move the right pointer until it reaches a letter.
The same logic applies on the right side. Non-letter characters are skipped because they should not move. 5. Swap the two letters.
Once both pointers point to letters, swap their values. This places the correct reversed letters into their target positions. 6. Move both pointers inward.
After a successful swap, increment the left pointer and decrement the right pointer so the algorithm continues processing the remaining characters. 7. Continue until the pointers cross.
When the pointers meet or cross, all letters have been reversed correctly, and the process is complete. 8. Convert the character array back into a string.
Return the final transformed string.
Why it works
The algorithm maintains an important invariant throughout execution: every processed letter pair has already been placed into its final reversed position, while all non-letter characters remain untouched. Since the left pointer always finds the next available letter from the front and the right pointer always finds the next available letter from the back, each swap correctly simulates reversing the sequence of letters. By the time the pointers cross, every letter has been reversed exactly once.
Python Solution
class Solution:
def reverseOnlyLetters(self, s: str) -> str:
characters = list(s)
left = 0
right = len(characters) - 1
while left < right:
while left < right and not characters[left].isalpha():
left += 1
while left < right and not characters[right].isalpha():
right -= 1
characters[left], characters[right] = (
characters[right],
characters[left],
)
left += 1
right -= 1
return "".join(characters)
The implementation begins by converting the string into a list called characters. This enables character swapping because Python strings cannot be modified directly.
Two pointers, left and right, are initialized at opposite ends of the list. The main loop continues while left < right.
Inside the loop, the first inner loop advances the left pointer until it points to a letter. The second inner loop moves the right pointer backward until it also points to a letter. These checks ensure that non-letter characters remain fixed in place.
Once both pointers reference letters, the characters are swapped. After the swap, both pointers move inward to continue processing the remaining portion of the string.
Finally, the modified character list is joined back into a string and returned.
Go Solution
func reverseOnlyLetters(s string) string {
characters := []byte(s)
left := 0
right := len(characters) - 1
for left < right {
for left < right && !isLetter(characters[left]) {
left++
}
for left < right && !isLetter(characters[right]) {
right--
}
characters[left], characters[right] =
characters[right], characters[left]
left++
right--
}
return string(characters)
}
func isLetter(ch byte) bool {
return (ch >= 'a' && ch <= 'z') ||
(ch >= 'A' && ch <= 'Z')
}
The Go solution follows the same algorithmic structure as the Python version. Since Go strings are immutable, the string is converted into a []byte slice for in-place swapping.
Instead of using a built-in alphabetic check like Python's isalpha(), a helper function isLetter explicitly checks whether a byte falls within the ASCII ranges for uppercase or lowercase English letters.
Go does not have tuple assignment exactly like Python, but it still supports concise swapping syntax for slice elements.
Worked Examples
Example 1
Input:
s = "ab-cd"
Initial character array:
['a', 'b', '-', 'c', 'd']
| Step | Left | Right | Characters[left] | Characters[right] | Action | Array State |
|---|---|---|---|---|---|---|
| 1 | 0 | 4 | a | d | Swap | d b - c a |
| 2 | 1 | 3 | b | c | Swap | d c - b a |
Final result:
"dc-ba"
Example 2
Input:
s = "a-bC-dEf-ghIj"
Initial array:
a - b C - d E f - g h I j
| Step | Left Char | Right Char | Action | Result |
|---|---|---|---|---|
| 1 | a | j | Swap | j - b C - d E f - g h I a |
| 2 | b | I | Swap | j - I C - d E f - g h b a |
| 3 | C | h | Swap | j - I h - d E f - g C b a |
| 4 | d | g | Swap | j - I h - g E f - d C b a |
| 5 | E | f | Swap | j - I h - g f E - d C b a |
Final result:
"j-Ih-gfE-dCba"
Example 3
Input:
s = "Test1ng-Leet=code-Q!"
| Step | Left Char | Right Char | Action |
|---|---|---|---|
| 1 | T | Q | Swap |
| 2 | e | e | Swap |
| 3 | s | d | Swap |
| 4 | t | o | Swap |
| 5 | n | c | Swap |
| 6 | g | t | Swap |
| 7 | L | e | Swap |
| 8 | e | e | Swap |
| 9 | e | L | Swap |
| 10 | t | g | Swap |
Final result:
"Qedo1ct-eeLg=ntse-T!"
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Each character is visited at most once by each pointer |
| Space | O(n) | Mutable character array is required |
The time complexity is linear because the two pointers move inward without revisiting positions unnecessarily. Even though there are nested loops, each pointer only traverses the string once overall.
The space complexity is O(n) because strings are immutable in both Python and Go, requiring a mutable copy of the characters for swapping.
Test Cases
solution = Solution()
assert solution.reverseOnlyLetters("ab-cd") == "dc-ba" # basic example
assert solution.reverseOnlyLetters("a-bC-dEf-ghIj") == "j-Ih-gfE-dCba" # mixed symbols
assert solution.reverseOnlyLetters("Test1ng-Leet=code-Q!") == "Qedo1ct-eeLg=ntse-T!" # complex example
assert solution.reverseOnlyLetters("abc") == "cba" # all letters
assert solution.reverseOnlyLetters("---") == "---" # no letters
assert solution.reverseOnlyLetters("a") == "a" # single character
assert solution.reverseOnlyLetters("7_28]") == "7_28]" # only non-letters
assert solution.reverseOnlyLetters("A-b") == "b-A" # mixed uppercase
assert solution.reverseOnlyLetters("z") == "z" # single lowercase letter
assert solution.reverseOnlyLetters("M1") == "M1" # one letter and one digit
assert solution.reverseOnlyLetters("a!!!b") == "b!!!a" # multiple consecutive symbols
assert solution.reverseOnlyLetters("AbCd-Ef") == "fEdC-bA" # alternating case
| Test | Why |
|---|---|
"ab-cd" |
Validates basic reversal with one symbol |
"a-bC-dEf-ghIj" |
Tests multiple symbols and mixed case |
"Test1ng-Leet=code-Q!" |
Tests complex mixed characters |
"abc" |
Ensures normal reversal when all are letters |
"---" |
Ensures non-letter strings remain unchanged |
"a" |
Validates minimum-size input |
"7_28]" |
Confirms no accidental movement of symbols |
"A-b" |
Tests uppercase handling |
"z" |
Single-letter boundary case |
"M1" |
Letter followed by digit |
"a!!!b" |
Consecutive non-letter characters |
"AbCd-Ef" |
Mixed uppercase and lowercase reversal |
Edge Cases
A very important edge case is a string containing no letters at all, such as "123-+=". A naive implementation might attempt unnecessary swaps or fail when searching for letters that do not exist. The two-pointer approach handles this naturally because both pointers simply skip non-letter characters until they cross, leaving the string unchanged.
Another important case is a string containing only letters, such as "abcdef". In this scenario, the algorithm should behave exactly like a standard string reversal. Since every character qualifies as a letter, the pointers continuously swap characters from opposite ends until the reversal is complete.
Consecutive non-letter characters can also create subtle bugs. For example, "a---b" contains multiple symbols in the middle. Incorrect pointer movement could accidentally swap symbols or stop too early. The implementation avoids this by repeatedly advancing pointers until valid letters are found before performing any swap.
Mixed uppercase and lowercase letters are another potential source of confusion. The algorithm must preserve the exact character values while reversing positions. For example, "a-Bc" becomes "c-Ba", not "C-ba" or any case-transformed variation. Since the implementation swaps characters directly rather than modifying them, case preservation happens automatically.