917. Reverse Only Letters
Problem Description
The task is to reverse a string s
, but with specific constraints. Only the English letters (both lowercase and uppercase) in the string should be reversed; all other characters should stay in the same place as they were in the original string.
To illustrate, if we are given a string like "a-bC-dEf-ghIj", we want to reverse only the letters to get "j-Ih-gfE-dCba", keeping the hyphens (-
) in their original positions.
Intuition
To address the given problem, we consider a two-pointer approach. We start with two indexes: one at the beginning of the string (i
) and one at the end (j
).
We then move the two indexes towards the center of the string, pausing each time we approach a non-letter character and skipping over it.
When both i
and j
point to English letters, we swap them. We continue this process, incrementing i
and decrementing j
, until i
is no longer less than j
.
This approach ensures that the letters are reversed in place while non-letter characters remain untouched, thus satisfying both conditions set by the problem constraints.
Learn more about Two Pointers patterns.
Solution Approach
The solution employs a two-pointer technique, which is often used when we want to traverse an array or string from both ends and possibly meet in the middle. Below is the breakdown of the implementation steps:
-
First, we convert the string
s
into a list because strings in Python are immutable, and we want to be able to swap letters in place. -
We then initialize two pointers,
i
at the beginning of the list (0
) andj
at the end (len(s) - 1
). -
We use a
while
loop to iterate over the list as long asi
is less thanj
. -
Inside the loop, we use two more
while
loops to move thei
pointer forward and thej
pointer backward until they point to English letters. We use theisalpha()
method to check if a character is an English letter:- The first inner
while
loop incrementsi
ifs[i]
is not a letter. - The second inner
while
loop decrementsj
ifs[j]
is not a letter.
- The first inner
-
After both pointers
i
andj
point to letters, we swap the characters at these positions. -
We then increment
i
and decrementj
to continue the traversal. -
Once the
while
loop conditioni < j
is no longer satisfied (meaning we have either completed traversing the list or both pointers have met or crossed), we exit the loop. -
Finally, we use
''.join(s)
to convert the list back into a string and return it as the final output. This string now contains all non-letter characters in their original positions, with the letters reversed relative to their positions in the original string.
This approach is efficient because it only requires a single pass through the string, with a time complexity of O(n) where n is the length of the string. The space complexity is also O(n) due to the conversion of the string to a list, which is necessary for in-place swaps.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through the given solution approach using a shorter example string: "Ab3c-dE".
-
Convert the string
s
into a list:["A", "b", "3", "c", "-", "d", "E"]
-
Initialize our two pointers:
i
starts at index0
: (pointing to "A")j
starts at index6
(the last index, pointing to "E")
-
We enter the
while
loop sincei (0)
is less thanj (6)
. -
We start the inner loops to increment
i
and decrementj
while skipping non-letter characters:i
is at index0
, pointing to "A", which is a letter, so we don't move it.j
is at index6
, pointing to "E", which is also a letter, so we don't move it.
-
Both pointers are at English letters, so we swap them.
- The list now looks like this:
["E", "b", "3", "c", "-", "d", "A"]
- The list now looks like this:
-
Increment
i
to1
and decrementj
to5
.- Now,
i
is pointing to "b" andj
is pointing to "d".
- Now,
-
Repeat steps 4-6:
- Both
i
andj
point to letters again, so we swap:- The list after the swap:
["E", "d", "3", "c", "-", "b", "A"]
- The list after the swap:
- Increment
i
to2
and decrementj
to4
.
- Both
-
Now
i
is pointing to "3" which is not a letter, soi
moves forward to index3
(pointing to "c"). -
For
j
, it is pointing to "-", which is not a letter, soj
moves backward to index3
.- Both
i
andj
are now pointing to the same position, so there's no need for further swaps.
- Both
-
Since
i
is no longer less thanj
, thewhile
loop condition is not satisfied. We exit the loop. -
Finally, we convert the list back to a string:
''.join(s)
gives us "Ed3c-bA"
The final output "Ed3c-bA" shows that the letters have been reversed while the non-letter characters ("3" and "-") are in their original positions as expected.
Solution Implementation
1class Solution:
2 def reverseOnlyLetters(self, string: str) -> str:
3 # Convert the input string into a list of characters for easy manipulation
4 char_list = list(string)
5 # Initialize two pointers, one at the beginning and one at the end of the char_list
6 left_index, right_index = 0, len(char_list) - 1
7
8 # Loop until the two pointers meet or pass each other
9 while left_index < right_index:
10 # Move the left_index forward if the current character is not a letter
11 while left_index < right_index and not char_list[left_index].isalpha():
12 left_index += 1
13 # Move the right_index backward if the current character is not a letter
14 while left_index < right_index and not char_list[right_index].isalpha():
15 right_index -= 1
16 # If both the current characters are letters, swap them
17 if left_index < right_index:
18 char_list[left_index], char_list[right_index] = char_list[right_index], char_list[left_index]
19 # Move both pointers closer towards the center
20 left_index, right_index = left_index + 1, right_index - 1
21
22 # Join the list of characters back into a string and return it
23 return ''.join(char_list)
24
1class Solution {
2 public String reverseOnlyLetters(String str) {
3 // Convert the input string to a character array for easier manipulation.
4 char[] characters = str.toCharArray();
5
6 // Initialize two pointers.
7 int left = 0; // The beginning of the string
8 int right = str.length() - 1; // The end of the string
9
10 // Use a while loop to iterate over the character array until the two pointers meet.
11 while (left < right) {
12 // Move the left pointer to the right as long as the current character isn't a letter.
13 while (left < right && !Character.isLetter(characters[left])) {
14 left++;
15 }
16
17 // Move the right pointer to the left as long as the current character isn't a letter.
18 while (left < right && !Character.isLetter(characters[right])) {
19 right--;
20 }
21
22 // Once both pointers are at letters, swap the characters.
23 if (left < right) {
24 char temp = characters[left];
25 characters[left] = characters[right];
26 characters[right] = temp;
27
28 // Move both pointers towards the center.
29 left++;
30 right--;
31 }
32 }
33
34 // Convert the manipulated character array back to a string and return it.
35 return new String(characters);
36 }
37}
38
1#include <string> // Include necessary header
2using namespace std;
3
4class Solution {
5public:
6 // Function to reverse only the letters in a string, leaving other characters in place
7 string reverseOnlyLetters(string str) {
8 int left = 0; // Initialize left pointer
9 int right = str.size() - 1; // Initialize right pointer
10
11 // Iterate over the string with two pointers from both ends
12 while (left < right) {
13 // Move left pointer to the right as long as it points to a non-letter
14 while (left < right && !isalpha(str[left])) {
15 ++left;
16 }
17
18 // Move right pointer to the left as long as it points to a non-letter
19 while (left < right && !isalpha(str[right])) {
20 --right;
21 }
22
23 // If both pointers are at letters, swap the letters and move pointers towards the center
24 if (left < right) {
25 swap(str[left], str[right]);
26 ++left;
27 --right;
28 }
29 }
30
31 // Return the modified string with letters reversed
32 return str;
33 }
34};
35
1function reverseOnlyLetters(s: string): string {
2 const stringLength: number = s.length; // Length of the input string
3 let leftIndex: number = 0; // Initialize left pointer
4 let rightIndex: number = stringLength - 1; // Initialize right pointer
5 let reversedArray = [...s]; // Convert string to array for easy manipulation
6
7 // Loop through the array to reverse only the letters
8 while (leftIndex < rightIndex) {
9 // Increment left pointer if current character is not a letter, until it points to a letter
10 while (!/[a-zA-Z]/.test(reversedArray[leftIndex]) && leftIndex < rightIndex) {
11 leftIndex++;
12 }
13
14 // Decrement right pointer if current character is not a letter, until it points to a letter
15 while (!/[a-zA-Z]/.test(reversedArray[rightIndex]) && leftIndex < rightIndex) {
16 rightIndex--;
17 }
18
19 // Swap the letters at leftIndex and rightIndex
20 [reversedArray[leftIndex], reversedArray[rightIndex]] = [reversedArray[rightIndex], reversedArray[leftIndex]];
21
22 // Move pointers towards the center
23 leftIndex++;
24 rightIndex--;
25 }
26
27 // Join the array back into a string and return the result
28 return reversedArray.join('');
29}
30
Time and Space Complexity
The given Python code defines a function reverseOnlyLetters
that takes a string s
, reverses only the alphabetic characters in it while leaving the other characters in their original positions, and then returns the modified string.
Time Complexity:
The time complexity of this function is O(n)
, where n
is the length of the string s
. Here's the breakdown:
- The function initially converts the string into a list, which takes
O(n)
time. - The while loop uses a two-pointer approach, with
i
starting at the beginning of the string andj
at the end. The loop runs untili
is less thanj
. Within the loop, there are operations of checking whether a character is alphabetical (s[i].isalpha()
ands[j].isalpha()
) and swapping the characters if both are letters. Both of these operations areO(1)
. - The loop will iterate at most
n/2
times because oncei
meetsj
in the middle, the process is complete. Each iteration has constant work (checking and swapping), thus the total time for the loop isO(n/2)
, which simplifies toO(n)
.
Therefore, combining the initial list conversion and the while loop, the overall time complexity remains O(n)
.
Space Complexity:
The space complexity of the function is also O(n)
for the following reasons:
- The function allocates space for a list of characters from the original string
s
, which isO(n)
space. - The space for the pointers
i
andj
is negligible (constant space, orO(1)
). - The list is converted back to a string at the end, but this does not require extra space proportional to
n
as the list is transformed in place.
Hence, the additional space required is proportional to the size of the input, leading to a space complexity of O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following is a min heap?
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!