Teaching Kids Programming – Reverse Only Letters via Two Pointer Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

Example 1:
Input: s = “ab-cd”
Output: “dc-ba”

Example 2:
Input: s = “a-bC-dEf-ghIj”
Output: “j-Ih-gfE-dCba”

Example 3:
Input: s = “Test1ng-Leet=code-Q!”
Output: “Qedo1ct-eeLg=ntse-T!”

Hints:
This problem is exactly like reversing a normal string except that there are certain characters that we have to simply skip. That should be easy enough to do if you know how to reverse a string using the two-pointer approach.

Algorithm to Reverse Only Letters in a String

We can skip the non-English letters and then swap the characters at two pointers. String is immutable and thus we convert the original string into a list, and then after reversal, we convert the list to string via the join function.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def reverseOnlyLetters(self, s: str) -> str:
        a = list(s)
        i, j = 0, len(a) - 1
        while i < j:
            while i < j and not a[i].isalpha():
                i += 1
            while i < j and not a[j].isalpha():
                j -= 1
            a[i], a[j] = a[j], a[i]
            i += 1
            j -= 1
        return "".join(a)

class Solution:
    def reverseOnlyLetters(self, s: str) -> str:
        a = list(s)
        i, j = 0, len(a) - 1
        while i < j:
            while i < j and not a[i].isalpha():
                i += 1
            while i < j and not a[j].isalpha():
                j -= 1
            a[i], a[j] = a[j], a[i]
            i += 1
            j -= 1
        return "".join(a)

The time complexity is O(N) and the space complexity is O(N) due to extra space for storing characters in a list.

See also: How to Reverse Only Letters in a String?

–EOF (The Ultimate Computing & Technology Blog) —