Problem statement

https://leetcode.com/problems/reverse-only-letters/

Solution

The idea is to collect all letters from our string s and put them into stack. Then we iterate string once again and:

  1. If we have letter, extract new element from the top of the stack and add it to answer.
  2. If we have other element, just add it to answer.
  3. In the end join all elements in answer.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def reverseOnlyLetters(self, s):
        stack = [c for c in s if c.isalpha()]
        return "".join(stack.pop() if c.isalpha() else c for c in s)