Remove Characters from first String present in the Second String

Problem Statement: Given two strings, write a program to remove characters from the first string which are present in the second string.

Examples:

Example 1:
Input: String str1 = “abcdef”
       String str2 = “cefz”
Output: abd
Explanation: The common characters in both strings are c, e, f.
So after removing these characters from string 1 we get string resulting string as abd.


Example 2:
Input: String str1 = “xyzpw”
       String str2 = “lmno”
Output: xyzpw
Explanation: As there is no common character in both the strings, string 1 remains unchanged.

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1:

Approach:

Keep on iterating string1(outer for loop) and set the flag to 0

In the inner for loop iterate through string2

If any element of string2 matches the corresponding character of string1 then set the flag to 1

After completion of the inner for loop, if the flag is not equal to 1 i.e if the corresponding string1 character is not present in string2 then add that character to the resulting string.

Return the resulting string after the iteration of loops is completed.

Code:

C++ Code

#include<bits/stdc++.h>

using namespace std;
string solve(string str1, string str2) {
  string ans;
  for (int i = 0; i < str1.length(); i++) {
    int flag = 0;
    for (int j = 0; j < str2.length(); j++) {
      if (str1[i] == str2[j]) {
        flag = 1;
      }
    }
    if (flag != 1)
      ans.push_back(str1[i]);
  }
  return ans;
}
int main() {

  // Input string
  string str1 = "abcdef";
  string str2 = "cefz";

  cout << "Final string 1:" << "\n";
  cout << solve(str1, str2) << "\n";
  return 0;
}

Output:

Final string 1:
abd

Time Complexity: O(m*n), m is the length of string 1, and n is the length of string 2

Space Complexity: O(n) for string ans in C++

Java Code

import java.util.*;
public class rem_char_2_str1 {
  public static String solve(String str1, String str2) {
    StringBuffer ans = new StringBuffer();
    for (int i = 0; i < str1.length(); i++) {
      int flag = 0;
      for (int j = 0; j < str2.length(); j++) {
        if (str1.charAt(i) == str2.charAt(j)) {
          flag = 1;
        }
      }

      if (flag != 1)
        ans.append(str1.charAt(i));
    }
    return ans.toString();
  }

  public static void main(String args[]) {
    String str1 = "abcdef";
    String str2 = "cefz";

    System.out.println("Final string 1:");
    System.out.println(solve(str1, str2));
  }
}

Output:

Final string 1:
abd

Time Complexity: O(m*n), m is the length of string 1, and n is the length of string 2

Space Complexity: O(n) for StringBuffer in java

Solution 2: Optimized

Approach:

Using HashMap in Java , unordered_map in C++

Hashmap / unordered_map actually helps us to keep the record of string2 characters, which we will eventually compare with string1 characters to find the common characters

Declare the hashmap wherein the keys will be the string2 characters and its corresponding value will be 1.

Now,iterate through string1 and if that character is not present in the HashMap / unordered_map then add that character to the resulting string.

Return the resulting string after the iteration of string1 is over.

Code:

C++ Code

#include<bits/stdc++.h>

using namespace std;
string solve(string str1, string str2) {
  unordered_map < char, int > mp;
  string ans = "";
  for (int i = 0; i < str2.length(); i++) {
    mp[str2[i]] = 1;
  }
  for (int i = 0; i < str1.length(); i++) {
    if (!mp[str1[i]]) {
      ans.push_back(str1[i]);
    }
  }
  return ans;
}
int main() {

  // Input string
  string str1 = "abcdef"; // string 1
  string str2 = "cefz"; // string 2

  cout << "Final string 1:" << "\n";
  cout << solve(str1, str2) << "\n";
  return 0;
}

Output:

Final string 1:
abd

Time Complexity: O(n)

Space Complexity: O(n) for unordered_map in C++

Java Code

import java.util.*;
public class tUf {
  public static String solve(String str1, String str2) {
    HashMap < Character, Integer > mp = new HashMap < > ();
    StringBuffer ans = new StringBuffer();
    for (int i = 0; i < str2.length(); i++) {
      mp.put(str2.charAt(i), 1);
    }
    for (int i = 0; i < str1.length(); i++) {
      if (mp.get(str1.charAt(i)) == null)
        ans.append(str1.charAt(i));
    }
    return ans.toString();
  }

  public static void main(String args[]) {
    String str1 = "abcdef"; // string 1
    String str2 = "cefz"; // string 2

    System.out.println("Final string 1:");
    System.out.println(solve(str1, str2));
  }
}

Output:

Final string 1:
abd

Time Complexity: O(n)

Space Complexity: O(n) for HashMap in Java

Special thanks to Rishiraj Girmal for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article