844. Backspace String Compare

class Solution:
    def backspaceCompare(self, S: str, T: str) -> bool:
        """tc O(N+M) sc O(N+M) : N: length of S, M:  length of T
        main idea: two ptr get each string's final revised string, compare 
        1. right ptr keep loop to the end 
        2. if s[r] != #, left ptr forward 1 step 
        3. if s[r] == #, left ptr back 1 step (assume l > 0)
        4. compare modified string returned back is same as the other one 
        """
        def helper(S):
            n = len(S)
            l = 0 
            for r in range(n):
                if S[r] != '#':
                    S[l] = S[r]
                    l += 1 
                elif S[r] == '#' and l > 0:
                    l -= 1
            return ''.join(S[:l])
                
        SS = helper(list(S))
        #print(SS)
        TT  = helper(list(T))
        #print(TT)
        return SS == TT

# time O(N) space O(1)
"""
1.get S,T's last position rs, rt  
2. Before rs,rt not run to the very begining of string, each time pass current right ptr and target string to get valid char and next right ptr. 
3. compare each time new valid char we get, if any of time ch1 != ch2, return False. 
4. until both rs, rt run out if we still can't find any diff, return True 

* in sub function, assuming before right ptr not run out or valid char not retrieved, use a cnt to record acuumutive # (each time encounter # +1, each time a non # -1 ) until cnt == 0 again.
 
 return char at cnt == 0 and next new right ptr   

"""
class Solution:
    def backspaceCompare(self, S: str, T: str) -> bool:
        def getChar(S,r):
            #r = len(S) -1
            cnt = 0
            char = ''
            while r >= 0 and not char:
                if S[r] == '#':
                    cnt += 1
                elif cnt == 0:
                    char = S[r]
                else:
                    cnt -=1 
                r -= 1 
            return char,r 
        rs,rt=  len(S)-1, len(T) -1
        while rs >= 0 or rt >= 0: 
            ch1 = ch2 = ''
            if rs >= 0: # can be removed for shorter 
                ch1, rs = getChar(S,rs)
            if rt >= 0:
                ch2, rt = getChar(T,rt)
            if ch1 != ch2:
                return False
        return True