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
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 startsint 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
truefor 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
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 startsint 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.
Be the first to add a comment.