Funcia
Lv.1stackstringtwo-pointers

Backspace Compare

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

Two people typed on a keyboard; their keystrokes are the strings s and t. A lowercase letter types that letter and # is a backspace, which deletes the letter typed just before it (a backspace with nothing to delete does nothing).

Return true if both people end up with the same text, otherwise false.

Examples

stresult
"ab#c""ad#c"true
"ab##""c#d#"true
"a#c""b"false

Example 2 — both texts end up empty.

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(s: string, t: string) → bool

Constraints

  • 1≤1 \le s.length, t.length ≤500,000\le 500{,}000
  • s and t consist only of lowercase English letters and #.

Expected complexity

Time
O(N + M)
Space
O(N + M)

Examples

stExpected
"ab#c""ad#c"true
"ab##""c#d#"true
"a#c""b"false

Hint

Hint

Typing a letter pushes it and a backspace pops the last one: process each string with a stack and compare the results. To use O(1)O(1) extra space, scan both strings from the end, counting how many letters are still to be skipped. Erasing characters from the middle of the string for each backspace shifts the tail every time, which is O(N2)O(N^2) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251000 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4012verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.