Compare Two Strings Boolean | Dataford Interview Questions

An agent editing a reply in the Intercom Inbox may use # to represent a backspace in a draft. Given two draft strings, determine whether they produce the same final text after processing every backspace.

A backspace removes the closest preceding character that has not already been removed. If no such character exists, the backspace has no effect. Comparison is case-sensitive, and the result must be returned as a boolean.

Formal Specification

Implement compare_drafts(first, second).

Input: two strings, first and second, containing lowercase English letters and # characters.
Output: True if both drafts resolve to the same final string, otherwise False.
Do not modify either input string.

Constraints

0 <= len(first), len(second) <= 10^5
Each character is a lowercase English letter or #
The input strings must not be modified
The target complexity is O(n + m) time and O(1) auxiliary space

Function Signature

def compare_drafts(first, second):

Your question is Compare Two Strings Boolean. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem