Given a string S, return the "reversed" string where all characters that are not a letter stay in the same place, and all letters reverse their positions.

Example 1: Input: "ab-cd" Output: "dc-ba" Example 2: Input: "a-bC-dEf-ghIj" Output: "j-Ih-gfE-dCba" Example 3: Input: "Test1ng-Leet=code-Q!" Output: "Qedo1ct-eeLg=ntse-T!"

class Solution {
    public String reverseOnlyLetters(String S) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < S.length(); i++) {
            if(Character.isLetter(S.charAt(i))) {
                stack.push(S.charAt(i));
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < S.length(); i++) {
            if(Character.isLetter(S.charAt(i))) {
                sb.append(stack.pop());
            } else {
                sb.append(S.charAt(i));
            }
        }

        return sb.toString();
    }
}