Remove Characters from First String Present in the Second String

16
0

Given two strings, str1 and str2, remove every character from str1 that appears in str2 and return the modified string.

Every occurrence of a common character must be removed, regardless of character frequency in either string. The relative order of the remaining characters in str1 must be preserved.

Example 1

Input: str1 = "banana", str2 = "ab"

Output: "nn"

Explanation: Characters 'a' and 'b' appear in both strings. Removing all occurrences of 'a' and 'b' from "banana" leaves "nn".

Example 2

Input: str1 = "xyzpw", str2 = "lmno"

Output: "xyzpw"

Explanation: No characters are common, so str1 remains unchanged.

Brute Force Approach

A straightforward way to solve the problem is to pick each character from the first string and look for the same character in the second string.

If a match is found, the character is ignored. Otherwise, the character is added to the result. Repeating the process for all characters removes every common character while keeping the original order of the remaining characters.

Algorithm

  • Start with an empty string to store the final result.

  • Pick each character from the first string, one at a time.

  • Check the current character against every character in the second string. Skip the character if a match is found; otherwise, add the character to the result.

  • Repeat the same process until all characters of the first string have been checked.

  • Return the final string containing only the remaining characters.

Dry Run

Remove Characters from First String Present in the Second String - Brute

Remove Characters from First String Present in the Second String - Brute

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Removes characters present in the second string
string removeCommonCharacters(string str1, string str2) {
// Stores the final result
string result = "";
// Traverse each character of the first string
for (char c : str1) {
bool found = false;
// Check the current character against the second string
for (char d : str2) {
// Check whether a matching character exists
if (c == d) {
found = true;
break;
}
}
// Append the character only if no match is found
if (!found) {
result += c;
}
}
// Return the modified string
return result;
}
};
// Driver code starts
int main() {
Solution sol;
string str1 = "banana";
string str2 = "ab";
// Call the function and print the result
cout << sol.removeCommonCharacters(str1, str2) << endl;
return 0;
}

Complexity Analysis

Let N represent the length of the first string and M represent the length of the second string.

• Time Complexity: O(N × M), as every character of the first string is compared with the characters of the second string in the worst case.

• Space Complexity: O(N), as the result string may store up to N characters in the worst case. The auxiliary space used is O(1).

Optimal Approach

The brute force approach works by checking every character of the first string against the second string. However, repeated searches make the approach slow, especially when both strings are large. Instead of searching the second string again and again, a better idea is to store the characters of the second string for quick lookup.

Since the problem contains lowercase English letters, a boolean array of size 26 is enough to track character presence. Each letter gets a fixed position in the array, and the position is marked as true when the letter appears in the second string. This makes character lookup constant time and helps reduce the overall time complexity.

Algorithm

  • Create a boolean array of size 26, initialized with false, to track the presence of characters.

  • Traverse the second string and mark the corresponding array position as true for every character.

  • Traverse the first string and check the corresponding array position for each character. Skip characters marked as true; otherwise, add the characters to the result.

  • Continue the process until every character of the first string has been checked.

  • Return the final result containing only the characters absent from the second string.

Dry Run

Remove Characters from First String Present in the Second String - Optimal

Remove Characters from First String Present in the Second String - Optimal

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Removes characters present in the second string
string removeCommonCharacters(string str1, string str2) {
// Stores the presence of lowercase English letters
bool present[26] = {false};
// Mark every character of the second string
for (char c : str2) {
present[c - 'a'] = true;
}
// Stores the final result
string result = "";
// Traverse each character of the first string
for (char c : str1) {
// Check whether the character is absent from the second string
if (!present[c - 'a']) {
result += c;
}
}
// Return the modified string
return result;
}
};
// Driver code starts
int main() {
Solution sol;
string str1 = "banana";
string str2 = "ab";
// Call the function and print the result
cout << sol.removeCommonCharacters(str1, str2) << endl;
return 0;
}

Complexity Analysis

Let N represent the length of the first string and M represent the length of the second string.

• Time Complexity: O(N + M), as the second string is traversed once to mark character presence, followed by a single traversal of the first string to build the result. Each array lookup takes O(1) time.

• Space Complexity: O(N), as the result string may store up to N characters in the worst case. The boolean array requires only O(1) auxiliary space because the array always contains exactly 26 elements.

Interview follow-up Questions

Yes, but the character mapping needs to be adjusted. For uppercase English letters, a separate range can be used in the character array, or a hash set can be used to support a wider range of characters.

StringTCS NQT

Read Similar Blogs

Comments0