917. Reverse Only Letters

EasyTwo PointersString
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

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:

  1. 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.

  2. We then initialize two pointers, i at the beginning of the list (0) and j at the end (len(s) - 1).

  3. We use a while loop to iterate over the list as long as i is less than j.

  4. Inside the loop, we use two more while loops to move the i pointer forward and the j pointer backward until they point to English letters. We use the isalpha() method to check if a character is an English letter:

    • The first inner while loop increments i if s[i] is not a letter.
    • The second inner while loop decrements j if s[j] is not a letter.

  5. After both pointers i and j point to letters, we swap the characters at these positions.

  6. We then increment i and decrement j to continue the traversal.

  7. Once the while loop condition i < j is no longer satisfied (meaning we have either completed traversing the list or both pointers have met or crossed), we exit the loop.

  8. 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Example Walkthrough

Let's go through the given solution approach using a shorter example string: "Ab3c-dE".

  1. Convert the string s into a list: ["A", "b", "3", "c", "-", "d", "E"]

  2. Initialize our two pointers:

    • i starts at index 0: (pointing to "A")
    • j starts at index 6 (the last index, pointing to "E")

  3. We enter the while loop since i (0) is less than j (6).

  4. We start the inner loops to increment i and decrement j while skipping non-letter characters:

    • i is at index 0, pointing to "A", which is a letter, so we don't move it.
    • j is at index 6, pointing to "E", which is also a letter, so we don't move it.

  5. Both pointers are at English letters, so we swap them.

    • The list now looks like this: ["E", "b", "3", "c", "-", "d", "A"]

  6. Increment i to 1 and decrement j to 5.

    • Now, i is pointing to "b" and j is pointing to "d".

  7. Repeat steps 4-6:

    • Both i and j point to letters again, so we swap:
      • The list after the swap: ["E", "d", "3", "c", "-", "b", "A"]
    • Increment i to 2 and decrement j to 4.

  8. Now i is pointing to "3" which is not a letter, so i moves forward to index 3 (pointing to "c").

  9. For j, it is pointing to "-", which is not a letter, so j moves backward to index 3.

    • Both i and j are now pointing to the same position, so there's no need for further swaps.

  10. Since i is no longer less than j, the while loop condition is not satisfied. We exit the loop.

  11. 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
Not Sure What to Study? Take the 2-min Quiz：

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

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 and j at the end. The loop runs until i is less than j. Within the loop, there are operations of checking whether a character is alphabetical (s[i].isalpha() and s[j].isalpha()) and swapping the characters if both are letters. Both of these operations are O(1).
  • The loop will iterate at most n/2 times because once i meets j in the middle, the process is complete. Each iteration has constant work (checking and swapping), thus the total time for the loop is O(n/2), which simplifies to O(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 is O(n) space.
  • The space for the pointers i and j is negligible (constant space, or O(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.

Fast Track Your Learning with Our Quick Skills Quiz:

A heap is a ...?

Recommended Readings

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 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 Two pointers is a common interview technique

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫