package pkg;

import java.util.Iterator;
import java.util.Stack;

public class RemoveToken {
    public static void main(String[] args) {
        final String s1 = "a#aayf#c#";
        final String s2 = "aa#ayy#k#pp##";

        System.out.println(backSpaceString(s1,s2));
    }
    static int backSpaceString(final String s1, final String s2){
        return reduceStr(s2).equals(reduceStr(s1))? 1: 0;
    }

    static String reduceStr(final String str) {
        final Stack<Character> stringStack = new Stack<>();
        final Stack<Character> hashStack = new Stack<>();
        final Stack<Character> resultStack = new Stack<>();

        for( char c : str.toCharArray()){
            stringStack.push(c);
        }
        if (!stringStack.contains('#')){
            return str;
        }

        boolean keepRunning = true;
        while(keepRunning){
            if(stringStack.isEmpty() && hashStack.isEmpty()) {
                keepRunning = false;
            }

            if(!stringStack.isEmpty() && stringStack.peek() != '#'){
                resultStack.push(stringStack.pop());
            }
            if(!stringStack.isEmpty() && stringStack.peek() == '#'){
                hashStack.push(stringStack.pop());
            }
            if(!resultStack.isEmpty() && !hashStack.isEmpty() && resultStack.peek() != '#'){
                hashStack.pop();
                resultStack.pop();
            }

        }
        final Iterator<Character> it = resultStack.iterator();
        final StringBuilder sb = new StringBuilder();
        while(it.hasNext()){
            sb.append(it.next());
        }
        return sb.reverse().toString();
    }
}