[AlgoMastery]
Topics›String›Backspace String Compare
📖

Backspace String Compare

String
~20 min read
5 practice problems

Overview

Backspace String Compare problems involve processing strings where '#' represents a backspace character that deletes the previous character. These problems test your understanding of string manipulation, stack operations, and two-pointer techniques.

Key challenges:

  • Simulating backspace operations
  • Comparing strings after processing
  • Handling multiple consecutive backspaces
  • Space-efficient solutions
  • Edge cases (empty strings, all backspaces)

Common backspace problems include:

  • Compare two strings after backspace processing
  • Build final string after backspaces
  • Minimum operations to make strings equal
  • Typed out strings comparison
  • Editor simulation

Pattern 1: Basic Backspace String Compare

Compare two strings after processing backspace characters.

Stack-based approach:

function backspaceCompare(s: string, t: string): boolean {
  return processBackspace(s) === processBackspace(t);
}

function processBackspace(s: string): string {
  const stack: string[] = [];
  
  for (const char of s) {
    if (char === '#') {
      if (stack.length > 0) {
        stack.pop();
      }
    } else {
      stack.push(char);
    }
  }
  
  return stack.join('');
}

Time: O(n + m), Space: O(n + m)

Two-pointer approach (space-optimized):

function backspaceCompareOptimized(s: string, t: string): boolean {
  let i = s.length - 1;
  let j = t.length - 1;
  
  while (i >= 0 || j >= 0) {
    // Process backspaces in s
    let skipS = 0;
    while (i >= 0) {
      if (s[i] === '#') {
        skipS++;
        i--;
      } else if (skipS > 0) {
        skipS--;
        i--;
      } else {
        break;
      }
    }
    
    // Process backspaces in t
    let skipT = 0;
    while (j >= 0) {
      if (t[j] === '#') {
        skipT++;
        j--;
      } else if (skipT > 0) {
        skipT--;
        j--;
      } else {
        break;
      }
    }
    
    // Compare characters
    if (i >= 0 && j >= 0) {
      if (s[i] !== t[j]) return false;
    } else if (i >= 0 || j >= 0) {
      return false;
    }
    
    i--;
    j--;
  }
  
  return true;
}

Time: O(n + m), Space: O(1)

Pattern 2: Build Final String After Backspaces

Construct the final string after processing all backspaces.

function buildStringAfterBackspace(s: string): string {
  const result: string[] = [];
  
  for (const char of s) {
    if (char === '#') {
      if (result.length > 0) {
        result.pop();
      }
    } else {
      result.push(char);
    }
  }
  
  return result.join('');
}

Time: O(n), Space: O(n)

In-place processing (simulated):

function buildStringInPlace(s: string): string {
  const chars = s.split('');
  let writeIndex = 0;
  
  for (let readIndex = 0; readIndex < chars.length; readIndex++) {
    if (chars[readIndex] === '#') {
      if (writeIndex > 0) {
        writeIndex--;
      }
    } else {
      chars[writeIndex] = chars[readIndex];
      writeIndex++;
    }
  }
  
  return chars.slice(0, writeIndex).join('');
}

Time: O(n), Space: O(n) for result

Pattern 3: Count Valid Characters After Backspaces

Count how many characters remain after processing backspaces.

function countValidCharacters(s: string): number {
  let count = 0;
  
  for (let i = 0; i < s.length; i++) {
    if (s[i] === '#') {
      if (count > 0) count--;
    } else {
      count++;
    }
  }
  
  return count;
}

Time: O(n), Space: O(1)

Count from right to left:

function countValidCharactersReverse(s: string): number {
  let count = 0;
  let skip = 0;
  
  for (let i = s.length - 1; i >= 0; i--) {
    if (s[i] === '#') {
      skip++;
    } else if (skip > 0) {
      skip--;
    } else {
      count++;
    }
  }
  
  return count;
}

Pattern 4: Multiple Backspace Characters

Handle cases where multiple '#' characters appear consecutively.

function processMultipleBackspaces(s: string): string {
  const result: string[] = [];
  
  for (const char of s) {
    if (char === '#') {
      // Pop as many as needed (already handled by while loop)
      if (result.length > 0) {
        result.pop();
      }
    } else {
      result.push(char);
    }
  }
  
  return result.join('');
}

Count-based approach:

function processBackspaceCount(s: string): string {
  const result: string[] = [];
  let backspaceCount = 0;
  
  for (let i = s.length - 1; i >= 0; i--) {
    if (s[i] === '#') {
      backspaceCount++;
    } else if (backspaceCount > 0) {
      backspaceCount--;
    } else {
      result.unshift(s[i]);
    }
  }
  
  return result.join('');
}

Pattern 5: Typed Out Strings

Compare strings that were typed out with backspace operations.

function typedOutStringsEqual(s: string, t: string): boolean {
  return buildTypedString(s) === buildTypedString(t);
}

function buildTypedString(s: string): string {
  const stack: string[] = [];
  
  for (const char of s) {
    if (char === '#') {
      stack.pop();
    } else {
      stack.push(char);
    }
  }
  
  return stack.join('');
}

Optimized comparison without building strings:

function typedOutStringsEqualOptimized(s: string, t: string): boolean {
  let i = s.length - 1;
  let j = t.length - 1;
  
  while (i >= 0 || j >= 0) {
    i = getNextValidIndex(s, i);
    j = getNextValidIndex(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;
}

function getNextValidIndex(s: string, index: number): number {
  let skip = 0;
  
  while (index >= 0) {
    if (s[index] === '#') {
      skip++;
      index--;
    } else if (skip > 0) {
      skip--;
      index--;
    } else {
      break;
    }
  }
  
  return index;
}

Time: O(n + m), Space: O(1)

Pattern 6: Minimum Operations to Make Equal

Find minimum operations to make two strings equal using backspaces.

function minOperationsToEqual(s: string, t: string): number {
  const sFinal = processBackspace(s);
  const tFinal = processBackspace(t);
  
  if (sFinal === tFinal) return 0;
  
  // Calculate edit distance
  return editDistance(sFinal, tFinal);
}

function editDistance(s1: string, s2: string): number {
  const m = s1.length;
  const n = s2.length;
  const dp: number[][] = Array(m + 1)
    .fill(null)
    .map(() => Array(n + 1).fill(0));
  
  for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;
  
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
      }
    }
  }
  
  return dp[m][n];
}

Pattern 7: Backspace String with Constraints

Process backspaces with additional constraints.

Maximum backspaces:

function processBackspaceWithLimit(s: string, maxBackspaces: number): string {
  const result: string[] = [];
  let backspaceCount = 0;
  
  for (const char of s) {
    if (char === '#') {
      if (backspaceCount < maxBackspaces && result.length > 0) {
        result.pop();
        backspaceCount++;
      }
    } else {
      result.push(char);
      backspaceCount = 0;
    }
  }
  
  return result.join('');
}

Backspace only deletes one character:

function processSingleBackspace(s: string): string {
  const result: string[] = [];
  
  for (const char of s) {
    if (char === '#') {
      if (result.length > 0) {
        result.pop();
      }
      // Ignore if result is empty
    } else {
      result.push(char);
    }
  }
  
  return result.join('');
}

Pattern 8: Compare with Different Backspace Characters

Handle different backspace representations.

function compareWithCustomBackspace(s: string, t: string, backspaceChar: string = '#'): boolean {
  const process = (str: string): string => {
    const result: string[] = [];
    
    for (const char of str) {
      if (char === backspaceChar) {
        if (result.length > 0) {
          result.pop();
        }
      } else {
        result.push(char);
      }
    }
    
    return result.join('');
  };
  
  return process(s) === process(t);
}

Multiple backspace types:

function compareWithMultipleBackspaceTypes(
  s: string, 
  t: string, 
  backspaceChars: string[]
): boolean {
  const backspaceSet = new Set(backspaceChars);
  
  const process = (str: string): string => {
    const result: string[] = [];
    
    for (const char of str) {
      if (backspaceSet.has(char)) {
        if (result.length > 0) {
          result.pop();
        }
      } else {
        result.push(char);
      }
    }
    
    return result.join('');
  };
  
  return process(s) === process(t);
}

Pattern 9: Backspace String Validation

Validate if a string can be transformed to target using backspaces.

function canTransformToTarget(source: string, target: string): boolean {
  const processed = processBackspace(source);
  return processed === target;
}

function processBackspace(s: string): string {
  const stack: string[] = [];
  
  for (const char of s) {
    if (char === '#') {
      if (stack.length > 0) stack.pop();
    } else {
      stack.push(char);
    }
  }
  
  return stack.join('');
}

Check if transformation is possible:

function canTransform(source: string, target: string): boolean {
  // Process source
  const sourceFinal = processBackspace(source);
  
  // Check if target can be obtained by adding characters to sourceFinal
  if (sourceFinal.length > target.length) return false;
  
  let i = 0, j = 0;
  
  while (i < sourceFinal.length && j < target.length) {
    if (sourceFinal[i] === target[j]) {
      i++;
      j++;
    } else {
      j++;
    }
  }
  
  return i === sourceFinal.length;
}

Pattern 10: Longest Common Substring After Backspaces

Find longest common substring after processing backspaces.

function longestCommonSubstringAfterBackspace(s: string, t: string): string {
  const sFinal = processBackspace(s);
  const tFinal = processBackspace(t);
  
  return longestCommonSubstring(sFinal, tFinal);
}

function longestCommonSubstring(s1: string, s2: string): string {
  const m = s1.length;
  const n = s2.length;
  let maxLength = 0;
  let endIndex = 0;
  
  const dp: number[][] = Array(m + 1)
    .fill(null)
    .map(() => Array(n + 1).fill(0));
  
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
        if (dp[i][j] > maxLength) {
          maxLength = dp[i][j];
          endIndex = i - 1;
        }
      }
    }
  }
  
  if (maxLength === 0) return '';
  
  return s1.substring(endIndex - maxLength + 1, endIndex + 1);
}

Pattern 11: Backspace String with Undo

Handle undo operations along with backspaces.

class TextEditor {
  private text: string[];
  private history: string[];
  
  constructor() {
    this.text = [];
    this.history = [];
  }
  
  type(char: string): void {
    this.history.push(this.text.join(''));
    this.text.push(char);
  }
  
  backspace(): void {
    if (this.text.length > 0) {
      this.history.push(this.text.join(''));
      this.text.pop();
    }
  }
  
  undo(): void {
    if (this.history.length > 0) {
      const previous = this.history.pop()!;
      this.text = previous.split('');
    }
  }
  
  getText(): string {
    return this.text.join('');
  }
}

Pattern 12: Optimized Backspace Processing

Efficient processing for large strings.

Process in chunks:

function processBackspaceChunked(s: string, chunkSize: number = 1000): string {
  const result: string[] = [];
  
  for (let i = 0; i < s.length; i += chunkSize) {
    const chunk = s.substring(i, Math.min(i + chunkSize, s.length));
    const processed = processBackspace(chunk);
    
    // Merge with previous result, handling backspaces at boundaries
    for (const char of processed) {
      if (char === '#') {
        if (result.length > 0) result.pop();
      } else {
        result.push(char);
      }
    }
  }
  
  return result.join('');
}

Stream processing:

class BackspaceProcessor {
  private buffer: string[];
  
  constructor() {
    this.buffer = [];
  }
  
  processChar(char: string): void {
    if (char === '#') {
      if (this.buffer.length > 0) {
        this.buffer.pop();
      }
    } else {
      this.buffer.push(char);
    }
  }
  
  getResult(): string {
    return this.buffer.join('');
  }
  
  reset(): void {
    this.buffer = [];
  }
}

When to Use Backspace String Techniques

Use backspace processing when:

  • Problem mentions "backspace", "#", or "delete"
  • Need to compare strings after processing
  • Typed out strings comparison
  • Editor simulation problems
  • String transformation with deletions
  • Space-efficient string processing required

Template (Stack-based)

function backspaceTemplate(s: string): string {
  const stack: string[] = [];
  
  for (const char of s) {
    if (char === '#') {
      if (stack.length > 0) stack.pop();
    } else {
      stack.push(char);
    }
  }
  
  return stack.join('');
}

Template (Two-pointer)

function backspaceCompareTemplate(s: string, t: string): boolean {
  let i = s.length - 1;
  let j = t.length - 1;
  
  while (i >= 0 || j >= 0) {
    i = skipBackspaces(s, i);
    j = skipBackspaces(t, j);
    
    if (i < 0 && j < 0) return true;
    if (i < 0 || j < 0 || s[i] !== t[j]) return false;
    
    i--;
    j--;
  }
  
  return true;
}

function skipBackspaces(s: string, index: number): number {
  let skip = 0;
  
  while (index >= 0) {
    if (s[index] === '#') {
      skip++;
      index--;
    } else if (skip > 0) {
      skip--;
      index--;
    } else {
      break;
    }
  }
  
  return index;
}

Time and Space Complexity Summary

  • Stack-based: O(n) time, O(n) space
  • Two-pointer: O(n) time, O(1) space
  • Comparison: O(n + m) time, O(1) space (two-pointer)
  • Building string: O(n) time, O(n) space
  • Validation: O(n) time, O(n) space

Practice Tips

  1. Choose approach — Stack for clarity, two-pointer for space
  2. Process right to left — Easier to handle backspaces
  3. Handle edge cases — Empty strings, all backspaces
  4. Skip logic — Count backspaces and skip characters
  5. Compare efficiently — Don't build full strings if not needed
  6. Test thoroughly — Multiple consecutive backspaces

Common Mistakes

  1. Not handling empty stack — Check length before pop
  2. Wrong direction — Process from right to left for comparison
  3. Off-by-one errors — Careful with indices
  4. Building unnecessary strings — Use two-pointer for comparison
  5. Not counting skips — Track backspace count correctly

Related Concepts

  • Stack Operations — For backspace simulation
  • Two Pointers — For space-efficient comparison
  • String Manipulation — Basic string operations
  • String Comparison — Comparing processed strings

Backspace string problems are common in interviews. Master these patterns, and you'll be well-prepared for string manipulation questions involving deletion operations.

← PreviousAdvanced String MatchingNext →Valid Parentheses/String