You are given a string s made up of lowercase English letters and special characters (any character that is not a lowercase letter).

You need to perform the following two operations, in this exact order:

1. Reverse the lowercase letters. Take all the lowercase letters from s, reverse their order, and put them back into the positions that were originally occupied by letters. The positions of the special characters stay untouched during this step.
2. Reverse the special characters. Take all the special characters from s, reverse their order, and put them back into the positions that were originally occupied by special characters. The positions of the letters stay untouched during this step.

In other words, letters can only move into spots that held letters, and special characters can only move into spots that held special characters. Each group is independently reversed in place.

Return the final string after both reversals have been applied.

Example:

• If s = "ab!cd", the letters are a, b, c, d. Reversed, they become d, c, b, a, and they fill the letter positions in order, giving dc!ba. The single special character ! stays where it is (reversing one character changes nothing), so the result is "dc!ba".

The key observation is that the two reversal operations don't actually interfere with each other. Letters only move into letter positions, and special characters only move into special-character positions. So we can think about each group completely separately.

When we reverse a group and then place it back into the same set of positions in order, what really happens? The first position that belongs to that group ends up holding the last element of the group, the second position holds the second-to-last element, and so on. This is exactly the behavior of a stack: if we collect all the elements of a group into a list and then pop from the end, we hand out the elements in reverse order.

This gives us a clean idea. We make two collections:

• A list a holding all the letters in their original left-to-right order.
• A list b holding all the special characters in their original left-to-right order.

Then we walk through s one character at a time. Whenever we hit a letter position, we pop() the last letter from a; whenever we hit a special-character position, we pop() the last special character from b. Because pop() always removes from the back, the letters come out reversed, and the special characters come out reversed, each filling only their own positions.

This naturally produces both reversals at once in a single pass, without needing two separate reverse-and-reinsert steps, since reversing letters and reversing special characters are independent and can be handled together.

Pattern Learn more about Two Pointers patterns.

Solution 1: Simulation

We first store the letters and special characters from string s into two separate lists a and b respectively. Then we traverse the string s. If the current position is a letter, we pop the last letter from list a and place it back at that position; otherwise, we pop the last special character from list b and place it back at that position.

After the traversal is complete, we obtain the result string.

Step-by-step breakdown:

1. Build the two lists. We loop over every character c in s. We use c.isalpha() to decide which group it belongs to. Letters are appended to a, and special characters are appended to b. At this point, both lists hold their elements in original left-to-right order.

   a = []
   b = []
   for c in s:
       if c.isalpha():
           a.append(c)
       else:
           b.append(c)

2. Rebuild the string with reversal. We traverse s again. For each position, we check c.isalpha():

   • If it is a letter position, we call a.pop(), which removes and returns the last letter in a.
   • Otherwise, it is a special-character position, so we call b.pop(), returning the last special character in b.

   Because pop() always takes from the end of the list, the letters are handed out in reverse order, and the special characters are handed out in reverse order. Each element lands only in a position of its own type, which is exactly what the two reversal operations require.

   return ''.join(a.pop() if c.isalpha() else b.pop() for c in s)

Data structures used: two lists a and b, each used as a stack (we only push with append and remove with pop).

Complexity analysis:

• Time complexity: O(n), where n is the length of s. We make two passes over the string, and each append/pop operation is O(1).
• Space complexity: O(n), since the two lists together store all characters of s, plus the space for the output string.