Problem Statement

Given two strings, str1 and str2, remove all characters from str1 that are present in str2.

Examples

Example 1:

Input: str1 = "computer", str2 = "cat"
Output: "ompuer"

Example 2:

Input: str1 = "hello world", str2 = "ld"
Output: "heo wor"

Approaches

1️⃣ Using a Hash

Intuition:

Use a hash set to store all the characters of the second string (str2). Then iterate through the first string (str1) and build a result by including only the characters that are not in the hash set.

Steps:

1. Create a hash set (or an array of size 256 to store ASCII values) to store characters of str2.
2. Traverse str1 and check if each character is in the hash set.
3. If it is not in the hash set, append it to the result string.

Code:

#include <iostream>
#include <unordered_set>
#include <string>

std::string removeCharacters(const std::string& str1, const std::string& str2) {
    std::unordered_set<char> charsToRemove(str2.begin(), str2.end());  // Store characters to be removed
    std::string result;

    for (char ch : str1) {
        if (charsToRemove.find(ch) == charsToRemove.end()) {  // If character is not in the set
            result += ch;  // Append it to the result
        }
    }

    return result;
}

int main() {
    std::string str1 = "computer";
    std::string str2 = "cat";
    
    std::string result = removeCharacters(str1, str2);
    std::cout << "Resulting string: " << result << std::endl;

    return 0;
}

Complexity Analysis

• Time Complexity: O(n + m), where n is the length of str1 and m is the length of str2. Building the set takes O(m), and iterating through str1 takes O(n).
• Space Complexity: O(m), because we use a hash set to store the characters of str2.

2️⃣ Using Character Frequency Array

Intuition:

Similar to the hash set approach, but using a character frequency array (size 256 for ASCII) to mark the presence of characters.

Steps:

1. Create an array charPresence of size 256 (for all ASCII characters) initialized to false.
2. Traverse str2 and mark characters present in it by setting the corresponding indices in charPresence to true.
3. Traverse str1 and append characters to the result string only if they are not marked in charPresence.

Code:

#include <iostream>
#include <string>

std::string removeCharactersUsingArray(const std::string& str1, const std::string& str2) {
    bool charPresence[256] = {false};  // Boolean array to mark characters to remove

    for (char ch : str2) {
        charPresence[ch] = true;  // Mark characters present in str2
    }

    std::string result;
    for (char ch : str1) {
        if (!charPresence[ch]) {  // If character is not marked, add it to the result
            result += ch;
        }
    }

    return result;
}

int main() {
    std::string str1 = "hello world";
    std::string str2 = "ld";
    
    std::string result = removeCharactersUsingArray(str1, str2);
    std::cout << "Resulting string: " << result << std::endl;

    return 0;
}

Complexity Analysis

• Time Complexity: O(n + m), where n is the length of str1 and m is the length of str2.
• Space Complexity: O(1), since the charPresence array is always of fixed size (256).