Corrupted String Recovery — Problem Statement & Solution Guide

StringsMediumRECOVER 1777831512659

TimeO(n)

SpaceO(1)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Strings and solve the Corrupted String Recovery problem optimally.

TopicStrings

PatternRECOVER 1777831512659

TimeO(n)

SpaceO(1)

Problem Description

Given a string s that may be null or undefined, return a new string consisting of all characters of s except the symbols '#' and '*'. The relative order of the remaining characters must be preserved. If s is null or undefined, treat it as an empty string and return "". The input may contain letters, digits, spaces and the two special markers. The algorithm must run in O(|s|) time and use O(1) extra space besides the output string.

DSA Pattern Breakdown

"Corrupted String Recovery"

medium

WHY DOES IT MATTER?

Filtering streams of data while preserving order is a foundational pattern in text processing, log sanitization, and network packet inspection; mastering it prevents hidden quadratic costs in production code.

OPTIMIZATION CHALLENGE

The breakthrough is realizing you don’t need a secondary collection for intermediate results; by writing directly into the output buffer you eliminate the repeated copying that causes quadratic time.

REAL-WORLD CONNECTION

Think of a firewall that drops packets matching blacklisted signatures while forwarding the rest unchanged – the firewall scans each packet once and decides to forward or discard, mirroring the linear filter here.

In an interview, write the loop that uses an index to write into a pre‑allocated array; after the scan, slice the array to the final length – this shows you understand both time and space constraints.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem is a classic linear‑time filtering task. The optimal solution walks the input string once, copying every character that is not a forbidden marker ('#' or '*') into a result buffer, thereby preserving order while using only constant auxiliary space. Naïve approaches that repeatedly concatenate strings or use high‑level split/join operations allocate a new string on each iteration, which in languages with immutable strings leads to O(n²) time because each concatenation copies the entire accumulated result. By treating the output as a mutable array (or using a StringBuilder) and writing characters in place, we achieve the desired O(|s|) runtime and O(1) extra memory beyond the output itself.

The underlying algorithmic paradigm is a single‑pass filter, a special case of the two‑pointer technique where one pointer reads the input and the other writes the filtered output. This pattern scales to any situation where a subset of elements must be retained while discarding others, and it avoids the overhead of auxiliary data structures like queues or stacks. The key insight is that the relative order of retained characters is already satisfied by the natural left‑to‑right traversal, so no additional reordering step is required.

Interview Questions on This Problem

Q1How would you modify the solution if the set of forbidden characters could be any arbitrary set provided at runtime?

Store the forbidden characters in a hash set for O(1) lookup, then perform the same linear scan, checking each character against the set before copying it to the output buffer.

Q2What are the trade‑offs between using a StringBuilder versus pre‑allocating a character array for the result?

StringBuilder abstracts resizing and appending, which is convenient but may allocate extra capacity; a pre‑allocated char array sized to |s| guarantees no extra allocations and truly constant extra space, at the cost of an extra pass to compute the final length if you want a tightly sized string.

Q3Can this algorithm be parallelized for very large strings, and what challenges arise?

Parallelization is possible by partitioning the string into chunks, filtering each chunk independently, and then concatenating the filtered sub‑results; however, you must compute the prefix sums of retained lengths to know where each chunk’s output should be placed, adding coordination overhead that may outweigh benefits for typical input sizes.

Examples

Example 1

Input

"ab#c* d#e*"

Output

"abc de"

Explanation: Start with "ab#c* d#e*". Removing every '#' gives "abc* d*e*". Removing every '*' from that result yields "abc de". Spaces are retained because they are not markers.

Example 2

Input

"###***"

Output

Explanation: All characters are either '#' or '*'. After filtering them out, no characters remain, so the result is an empty string.

Example 3

Input

null

Output

Explanation: The input is null, which is interpreted as an empty string. Consequently the function returns an empty string.

Constraints

0 <= |s| <= 10^6
s contains only ASCII letters, digits, spaces, '#', and '*'

Optimal Approach & Strategy

Traverse once, copy allowed characters into a pre‑allocated buffer using a write index, then return the buffer up to that index, achieving linear time and constant extra space.

Brute Force Approach

Iterate over the string and build the answer by concatenating each non‑marker character to a new string; each concatenation creates a fresh copy, leading to quadratic time.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

function recoverString(s) {
    if (s == null) return "";
    let res = '';
    for (let i = 0; i < s.length; i++) {
        const ch = s[i];
        if (ch !== '#' && ch !== '*') res += ch;
    }
    return res;
}
const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });
let input = '';
rl.on('line', line => { input += line; });
rl.on('close', () => {
    console.log(recoverString(input));
});

#include <bits/stdc++.h>
using namespace std;

string recoverString(const string& s) {
    string res;
    res.reserve(s.size());
    for (char c : s) {
        if (c != '#' && c != '*') res.push_back(c);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    getline(cin, s);
    cout << recoverString(s) << "\n";
    return 0;
}

import java.io.*;

public class Main {
    public static String recoverString(String s) {
        if (s == null) return "";
        StringBuilder sb = new StringBuilder(s.length());
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c != '#' && c != '*') sb.append(c);
        }
        return sb.toString();
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        if (s == null) s = "";
        System.out.println(recoverString(s));
    }
}

import sys

def recover_string(s):
    if s is None:
        return ""
    return ''.join(ch for ch in s if ch not in ('#', '*'))

if __name__ == "__main__":
    s = sys.stdin.read()
    if s.endswith('\n'):
        s = s[:-1]
    print(recover_string(s))

function recoverString(s) {
    if (s == null) return "";
    let res = '';
    for (let i = 0; i < s.length; i++) {
        const ch = s[i];
        if (ch !== '#' && ch !== '*') res += ch;
    }
    return res;
}
const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });
let input = '';
rl.on('line', line => { input += line; });
rl.on('close', () => {
    console.log(recoverString(input));
});

Asked in Top Tech Interviews

AmazonRazorpay

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.