Reverse Only Letters LeetCode Solution

Difficulty Level Easy
Frequently asked in Amazon Apple Google MicrosoftViews 4577

Problem Statement

Reverse Only Letters LeetCode Solution – 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.
  • All the English letters (lowercase or uppercase) should be reversed.

Return s after reversing it.Reverse Only Letters LeetCode Solution

Input: s = "ab-cd"
Output: "dc-ba"

Explanation

Write the characters of S one by one. When we encounter a letter, we want to write the next letter that occurs if we iterated through the string backward.

So we do just that: keep track of a pointer j that iterates through the string backward. When we need to write a letter, we use it.

if we look closely we need to reverse the string but only consider letters so we can keep two pointers: one at the start and one at the end and then keep swapping values of start and end if they meet the given condition.

Another Approach:

Collect the letters of S separately into a stack, so that popping the stack reverses the letters. (Alternatively, we could have collected the letters into an array and reversed the array.)

Then, when writing the characters of S, any time we need a letter, we use the one we have prepared instead.

Code

C++ Code for Reverse Only Letters

class Solution {
public:
     string reverseOnlyLetters(string S) {
        for (int i = 0, j = S.length() - 1; i < j;) {
            if (!isalpha(S[i]))
                ++i;
            else if (!isalpha(S[j]))
                --j;
            else
                swap(S[i++], S[j--]);
        }
        return S;
    }
};

Java Code for Reverse Only Letters

class Solution {
    public String reverseOnlyLetters(String S) {
        StringBuilder sb = new StringBuilder(S);
        for (int i = 0, j = S.length() - 1; i < j;) {
            if (!Character.isLetter(sb.charAt(i))) {
                ++i;
            } else if (!Character.isLetter(sb.charAt(j))) {
                --j;
            } else {
                sb.setCharAt(i, S.charAt(j));
                sb.setCharAt(j--, S.charAt(i++));
            }
        }
        return sb.toString();
    }
}

Python Code for Reverse Only Letters

class Solution:
    def reverseOnlyLetters(self, S):
        S, i, j = list(S), 0, len(S) - 1
        while i < j:
            if not S[i].isalpha():
                i += 1
            elif not S[j].isalpha():
                j -= 1
            else:
                S[i], S[j] = S[j], S[i]
                i, j = i + 1, j - 1
        return "".join(S)

Complexity Analysis for Reverse Only Letters LeetCode Solution

Time Complexity

O(n/2) -> Single Pass

Space Complexity

O(1) -> no extra space is used other than two variables

Reference: https://algodaily.com/lessons/using-the-two-pointer-technique

Translate »