Given two strings S andT, return if they are equal when both are typed into empty text editors.#means a backspace character.

Example 1:

Input: 
S = 
"ab#c"
, T = 
"ad#c"
Output: 
true

Explanation
: Both S and T become "ac".

Example 2:

Input: 
S = 
"ab##"
, T = 
"c#d#"
Output: 
true

Explanation
: Both S and T become "".

Example 3:

Input: 
S = 
"a##c"
, T = 
"#a#c"
Output: 
true

Explanation
: Both S and T become "c".

Example 4:

Input: 
S = 
"a#c"
, T = 
"b"
Output: 
false

Explanation
: S becomes "c" while T becomes "b".

Note:

1. 1 < = S.length < = 200
2. 1 < = T.length < = 200
3. S and T only contain lowercase letters and '#' characters.

Follow up:

• Can you solve it in O(N) time and O(1) space?

class Solution {
    public boolean backspaceCompare(String S, String T) {
        int count1 = 0, count2 = 0;
        StringBuilder sb1 = new StringBuilder(), sb2 = new StringBuilder();

        for (int i = S.length() - 1; i >= 0; i--){
            char c = S.charAt(i);

            if (c == '#'){
                count1++;
            }
            else{
                if (count1 > 0){
                    count1--;
                }
                else{
                    sb1.append(c);
                }
            }
        }

        for (int i = T.length() - 1; i >= 0; i--){
            char c = T.charAt(i);

            if (c == '#'){
                count2++;
            }
            else{
                if (count2 > 0){
                    count2--;
                }
                else{
                    sb2.append(c);
                }
            }
        }

        return sb1.toString().equals(sb2.toString());
    }
}