Backspace String Compare

Easy
52.

Backspace String Compare

Backspace String Compare is an easy coding problem on strings, two pointers and stack.

Given two strings s and t, return true if they are equal when both are typed into empty text editors, where # means backspace.

Backspacing an empty editor leaves it empty.

Example 1

Input
s = "ab#c", t = "ad#c"
Output
true
Explanation
Both become "ac".

Example 2

Input
s = "ab##", t = "c#d#"
Output
true
Explanation
Both become "".

Example 3

Input
s = "a#c", t = "b"
Output
false

Constraints

  • 1 <= s.length, t.length <= 20
  • Lowercase letters and '#'.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var backspaceCompare = function(s, t) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Backspace String Compare — Solution in Python, Java & C++

Backspace String Compare solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Backspace String Compare is an easy coding problem on strings, two pointers and stack.

  • Difficulty: Easy
  • Topics: Strings, Two Pointers, Stack
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given two strings s and t, return true if they are equal when both are typed into empty text editors, where # means backspace.

Backspacing an empty editor leaves it empty.

Example 1

Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both become "ac".

Example 2

Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Both become "".

Example 3

Input: s = "a#c", t = "b"
Output: false

Constraints

  • 1 <= s.length, t.length <= 20
  • Lowercase letters and '#'.

Hints for Backspace String Compare

  1. Hint 1

    A stack simulates typing directly.

  2. Hint 2

    The O(1)-space version walks both strings backwards, counting pending backspaces.

How to solve Backspace String Compare

Scanning forwards is awkward because a backspace refers to something already typed. Scanning backwards fixes that: when you meet a # you know it will consume the next real character to the left, so carry a counter of pending deletions and skip that many characters. Walk both strings backwards in step and compare the surviving characters.

Approach

  1. Put i at the end of s and j at the end of t.
  2. Advance i leftwards to the next surviving character: a # increments a skip counter, and a normal character is discarded (decrementing the counter) while the counter is positive.
  3. Do the same for j in t.
  4. If both landed on a character, they must match; if only one did, the strings differ in length after editing — return false.
  5. Step both pointers past the compared characters and repeat until both are exhausted.

Why it works

Reading right to left makes each # refer to characters not yet visited, so the effect of every backspace is known before its victim is reached — no lookahead or rewriting is needed. The surviving characters emerge in reverse order of the final text, so comparing them pairwise is exactly comparing the two edited strings. Building both strings with a stack is equally correct and easier to write, at the cost of O(n) extra space.

Complexity

  • Time — O(|s| + |t|)
  • Space — O(1)

Pitfalls

  • The loop must continue while either pointer still has characters — stopping when one runs out misses a length mismatch.
  • Backspacing an empty editor is a no-op, which the counter handles by simply never going negative.
  • Consecutive #s stack up; the skip counter must accumulate rather than being a boolean.
  • After comparing a pair, move both pointers on — leaving one in place re-compares the same character.

Reference solution

Python

def backspaceCompare(s: str, t: str) -> bool:
    def build(x: str) -> str:
        st = []
        for ch in x:
            if ch == "#":
                if st:
                    st.pop()
            else:
                st.append(ch)
        return "".join(st)

    return build(s) == build(t)

Java

public static boolean backspaceCompare(String s, String t) {
    int i = s.length() - 1, j = t.length() - 1;
    while (i >= 0 || j >= 0) {
        int skip = 0;
        while (i >= 0) {
            if (s.charAt(i) == '#') {
                skip++;
                i--;
            } else if (skip > 0) {
                skip--;
                i--;
            } else break;
        }
        skip = 0;
        while (j >= 0) {
            if (t.charAt(j) == '#') {
                skip++;
                j--;
            } else if (skip > 0) {
                skip--;
                j--;
            } else break;
        }
        if (i >= 0 && j >= 0) {
            if (s.charAt(i) != t.charAt(j)) return false;
        } else if (i >= 0 || j >= 0) {
            return false;
        }
        i--;
        j--;
    }
    return true;
}

C++

bool backspaceCompare(string s, string t) {
    int i = (int) s.size() - 1, j = (int) t.size() - 1;
    while (i >= 0 || j >= 0) {
        int skip = 0;
        while (i >= 0) {
            if (s[i] == '#') {
                skip++;
                i--;
            } else if (skip > 0) {
                skip--;
                i--;
            } else break;
        }
        skip = 0;
        while (j >= 0) {
            if (t[j] == '#') {
                skip++;
                j--;
            } else if (skip > 0) {
                skip--;
                j--;
            } else break;
        }
        if (i >= 0 && j >= 0) {
            if (s[i] != t[j]) return false;
        } else if (i >= 0 || j >= 0) {
            return false;
        }
        i--;
        j--;
    }
    return true;
}

JavaScript

var backspaceCompare = function(s, t) {
    function build(x) {
        const st = [];
        for (const ch of x) {
            if (ch === "#") st.pop();
            else st.push(ch);
        }
        return st.join("");
    }
    return build(s) === build(t);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Two Pointers Technique