917. Reverse Only Letters

Approach 1: Front and Back switching

class Solution:
    def reverseOnlyLetters(self, S):
        """
        https://leetcode.com/problems/reverse-only-letters/description/
        :type S: str
        :rtype: str
        """
        if S == "":
            return ""
        S = list(S)
        i, j = 0, len(S) - 1
        while i < j:
            if S[i].isalpha() == False:
                i += 1
            if S[j].isalpha() == False:
                j -= 1
            else:
                S[i], S[j] = S[j], S[i]
                i += 1
                j -= 1
        return ''.join(S)

This approach required keeping track of two positions in the array where we stay until we can find valid characters, once we find two characters at the front and back, we will switch them.

Time Complexity: O(1), just indices

Space Complexity: O(n)

Approach 2: Minor improvements to Approach 1

Instead of increasing i and j one by one, it can be optimized by using nesting while loops to increment/decrement until the next character on both ends and swap when we find them

class Solution:
    def reverseOnlyLetters(self, S):
        """
        https://leetcode.com/problems/reverse-only-letters/description/
        :type S: str
        :rtype: str
        """
        if S == "": return ""
        le = len(S)
        S = list(S)
        i, j = 0, le - 1
        while i < j:
            while i < j and S[i].isalpha() == False:
                i += 1
            while j > i and S[j].isalpha() == False:
                j -= 1
            if i < j:
                S[i], S[j] = S[j], S[i]
                i += 1
                j -= 1
        return ''.join(S)

The runtime and space complexity remains the same

Time Complexity: O(1), just indices

Space Complexity: O(n)