< Back




917. Reverse Only Letters

Pretty fun problem, requires two-pointers to reverse a string, however, we've got to make some
decisions to conduct a no-op (no-operation) on non-alphabetic characters. We create a left and
right pointer and, while the pointers haven't crossed, we check to see if the characters at the left
and right pointer are alphabetic. If they both are, we swap the characters pointed to by the
pointers - an important distinction from the different decisions.

If the left pointer is non-alpha, but the right is, the left pointer is incrememnted. Same goes for
the right pointer. Finally, if both are non-alpha, we increment both pointers. These situations are
our no-op outcomes.

The solution is as follows:


  class Solution(object):
      def reverseOnlyLetters(self, S):
          ans = list(S)
          l, r = 0, len(ans) - 1

          while l < r:
              l_alpha, r_alpha = ans[l].isalpha(), ans[r].isalpha()

              if l_alpha and r_alpha:
                  ans[l], ans[r] = ans[r], ans[l]
                  l += 1
                  r -= 1
              elif l_alpha and not r_alpha:
                  r -= 1
              elif r_alpha and not l_alpha:
                  l += 1
              else:
                  l += 1
                  r -= 1

          return "".join(ans)


_ Time Complexity:

  O(n) - We iterate through the string once in O(n/2) time, which is O(n).

_ Space Complexity:

  O(n) - We convert the string to a list, storing n characters in memory.