Backspace Compare
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 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
| s | t | result |
|---|---|---|
"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
-
s.length,t.length sandtconsist only of lowercase English letters and#.
Expected complexity
- Time
- O(N + M)
- Space
- O(N + M)
Examples
| s | t | Expected |
|---|---|---|
"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 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 and exceeds the time limit.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1000 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 12 | verdict only |
| performance | 60 | 4 | verdict only |