Backspace String Compare - Practice Coding Problems

Backspace String Compare - Problem

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

Note: After backspacing an empty text, the text will continue to remain empty.

Follow up: Can you solve it in O(1) space?

Input & Output

Example 1 — Basic Backspace

$ Input: s = "ab#c", t = "ad#c"

› Output: true

💡 Note: Both strings become "ac" after processing backspaces: s removes 'b', t removes 'd'

Example 2 — Multiple Backspaces

$ Input: s = "ab##", t = "c#d#"

› Output: true

💡 Note: Both strings become empty after processing: s removes 'b' then 'a', t removes 'd' then 'c'

Example 3 — Different Results

$ Input: s = "a#c", t = "b"

› Output: false

💡 Note: s becomes "c" after removing 'a', t remains "b", so they are not equal

Constraints

1 ≤ s.length, t.length ≤ 200
s and t only contain lowercase letters and '#' characters

Visualization

Tap to expand

Understanding the Visualization

Input

Two strings with # representing backspaces

Process

Apply backspaces to build final strings

Compare

Check if final strings are equal

Key Takeaway

🎯 Key Insight: Process strings from right to left to handle backspaces efficiently without building intermediate strings

Asked in

G Google 25 f Facebook 20 a Amazon 15

The key insight is to process strings from right to left to handle backspaces naturally. Best approach uses two pointers from the end for O(1) space. Time: O(n + m), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers from End	O(n + m)	O(1)	Use two pointers from the end of both strings to compare characters while handling backspaces
Build Final Strings	O(n + m)	O(n + m)	Build both final strings after processing backspaces, then compare

Two Pointers from End — Algorithm Steps

Start two pointers at the end of both strings
Skip characters based on backspace count
Compare valid characters from both strings
Return true if all valid characters match

Visualization

Tap to expand

Step-by-Step Walkthrough

Start from End

Place pointers at end of both strings

Skip Backspaces

Move backwards while counting and applying backspaces

Compare Characters

Compare valid characters from both strings

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int getNextValidChar(const char* str, int index) {
    int backspaceCount = 0;
    while (index >= 0) {
        if (str[index] == '#') {
            backspaceCount++;
        } else if (backspaceCount > 0) {
            backspaceCount--;
        } else {
            break;
        }
        index--;
    }
    return index;
}

bool solution(char* s, char* t) {
    int i = strlen(s) - 1;
    int j = strlen(t) - 1;
    
    while (i >= 0 || j >= 0) {
        i = getNextValidChar(s, i);
        j = getNextValidChar(t, j);
        
        if (i < 0 && j < 0) return true;
        if (i < 0 || j < 0) return false;
        if (s[i] != t[j]) return false;
        
        i--;
        j--;
    }
    
    return true;
}

int main() {
    char s[201], t[201];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    fgets(t, sizeof(t), stdin);
    t[strcspn(t, "\n")] = 0;
    
    bool result = solution(s, t);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + m)

Single pass through both strings where n and m are lengths

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables for pointers and counters

✓ Linear Space

125.0K Views

Medium Frequency

~15 min Avg. Time

3.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pointers from End — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler