Given two strings str1 and str2, which are of lengths N and M. The second string contains all the characters of the first string, but there are some extra characters as well. The task is to find all the extra characters present in the second string.
Examples:
Input: str1 = “abcd”, str2 = “dabcdehi”
Output: d, e, h, i
Explanation: [d, e, h, i] are the letters that was added in string str2.
‘d’ is included because in str2 there is one extra ‘d’ than in str1.Input: str1 = “”, str2 = “y”
Output: y
Approach: The solution to this problem is based on the concept of hashing. Follow the steps mentioned below:
- Create an empty hash table of size 26 and increment all occurrences of each character of the first string (str1).
- Now traverse the second string (str2) and remove all characters of first string as well as add the new characters in the hash table.
- Remaining characters in the hash table are the extra characters.
Below is the implementation of the above approach
C++
// C++ program to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find the extra charactersvector<char> findTheDifference(string str1, string str2){ vector<int> vs(26, 0); vector<char> ans; // Loop to find the frequency // of characters in str1 for (int i = 0; i < str1.size(); i++) vs[str1[i] - 'a']++; // Adjusting frequency in str2 for (int i = 0; i < str2.size(); i++) { // If character was present in str1 if (vs[str2[i] - 'a'] > 0) vs[str2[i] - 'a']--; else vs[str2[i] - 'a']++; } // Loop to find the extra characters for (int i = 0; i < 26; i++) if (vs[i] > 0) ans.push_back(i + 'a'); return ans;}// Driver codeint main(){ // Given string string str1 = "abcd"; string str2 = "dabcdehi"; // Function call vector<char> ans = findTheDifference(str1, str2); for (char c : ans) cout << c << " "; return 0;} |
Java
// Java program to implement the approachimport java.util.*;class GFG { // Function to find the extra characters public static ArrayList<Character> findTheDifference(String str1, String str2) { ArrayList<Integer> vs = new ArrayList<>(); for (int i = 0; i < 26; i++) vs.add(0); ArrayList<Character> ans = new ArrayList<>(); // Loop to find the frequency // of characters in str1 for (int i = 0; i < str1.length(); i++) vs.set(str1.charAt(i) - 'a', vs.get(str1.charAt(i) - 'a') + 1); // Adjusting frequency in str2 for (int i = 0; i < str2.length(); i++) { // If character was present in str1 if (vs.get(str2.charAt(i) - 'a') > 0) vs.set(str2.charAt(i) - 'a', vs.get(str2.charAt(i) - 'a') - 1); else vs.set(str2.charAt(i) - 'a', vs.get(str2.charAt(i) - 'a') + 1); } // Loop to find the extra characters for (int i = 0; i < 26; i++) if (vs.get(i) > 0) { ans.add((char)(i + 97)); } return ans; } // Driver code public static void main(String[] args) { // Given string String str1 = "abcd"; String str2 = "dabcdehi"; // Function call ArrayList<Character> ans = findTheDifference(str1, str2); for (int i = 0; i < ans.size(); i++) { System.out.print((ans.get(i)) + " "); } }}// This code is contributed by Palak Gupta |
Python3
# python3 program to implement the approach# Function to find the extra charactersdef findTheDifference(str1, str2): vs = [0 for _ in range(26)] ans = [] # Loop to find the frequency # of characters in str1 for i in range(0, len(str1)): vs[ord(str1[i]) - ord('a')] += 1 # Adjusting frequency in str2 for i in range(0, len(str2)): # If character was present in str1 if (vs[ord(str2[i]) - ord('a')] > 0): vs[ord(str2[i]) - ord('a')] -= 1 else: vs[ord(str2[i]) - ord('a')] += 1 # Loop to find the extra characters for i in range(0, 26): if (vs[i] > 0): ans.append(chr(i + ord('a'))) return ans# Driver codeif __name__ == "__main__": # Given string str1 = "abcd" str2 = "dabcdehi" # Function call ans = findTheDifference(str1, str2) for c in ans: print(c, end=" ") # This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to find the extra characters static char[] findTheDifference(string str1, string str2) { char[] vs = new char[26]; for (int i = 0; i < 26; i++) { vs[i] = '0'; } char[] ans = new char[1000]; // Loop to find the frequency // of characters in str1 for (int i = 0; i < str1.Length; i++) vs[str1[i] - 'a']++; // Adjusting frequency in str2 for (int i = 0; i < str2.Length; i++) { // If character was present in str1 if (vs[str2[i] - 'a'] > 0) vs[str2[i] - 'a']--; else vs[str2[i] - 'a']++; } // Loop to find the extra characters for (int i = 0; i < 26; i++) if (vs[i] > 0) string.Concat(ans, i + 'a'); return ans; } // Driver Code public static void Main() { // Given string string str1 = "abcd"; string str2 = "dabcdehi"; // Function call char[] ans = findTheDifference(str1, str2); foreach (char c in ans) Console.Write(c + " "); }}// This code is contributed by sanjoy_62. |
Javascript
<script> // JavaScript code for the above approach // Function to find the extra characters function findTheDifference(str1, str2) { let vs = new Array(26).fill(0); let ans = []; // Loop to find the frequency // of characters in str1 for (let i = 0; i < str1.length; i++) vs[str1[i].charCodeAt(0) - 'a'.charCodeAt(0)]++; // Adjusting frequency in str2 for (let i = 0; i < str2.length; i++) { // If character was present in str1 if (vs[str2[i].charCodeAt(0) - 'a'.charCodeAt(0)] > 0) vs[str2[i].charCodeAt(0) - 'a'.charCodeAt(0)]--; else vs[str2[i].charCodeAt(0) - 'a'.charCodeAt(0)]++; } // Loop to find the extra characters for (let i = 0; i < 26; i++) if (vs[i] > 0) ans.push(String.fromCharCode(i + 'a'.charCodeAt(0))); return ans; } // Driver code // Given string let str1 = "abcd"; let str2 = "dabcdehi"; // Function call let ans = findTheDifference(str1, str2); for (let c of ans) document.write(c + " "); // This code is contributed by Potta Lokesh </script> |
Output
d e h i
Output
d e h i
Time Complexity: O(M)
Auxiliary Space: O(1).
METHOD: character count” or ” dictionary-based” approach.
The “character count” or “dictionary-based” approach is a method to find the extra characters in one string compared to another string. Here are the steps to implement this approach:
- Create two empty dictionaries count1 and count2.
- Iterate through the characters in the first string str1, and for each character:
a. Check if the character exists in the dictionary count1. If it does, increment its value by 1. If it doesn’t, add the character to the dictionary with a value of 1. - Repeat step 2 for the second string str2, but using the dictionary count2.
- Create an empty list extra_chars.
- Iterate through the keys in the dictionary count2, and for each key:
a. Check if the key exists in the dictionary count1. If it does, compare the value of the key in both dictionaries. If the value in count2 is greater than the value in count1, append the key to the list extra_chars. - Return the list extra_chars.
- The find_extra_chars function in the provided code follows these steps and returns a list of extra characters in str2 that are not present in str1.
C++
#include <iostream>#include <string>#include <unordered_map>#include <vector>std::vector<char> find_extra_chars(std::string str1, std::string str2) { std::unordered_map<char, int> count1, count2; // Count occurrences of each character in str1 for (char c : str1) { count1++; } // Count occurrences of each character in str2 for (char c : str2) { count2++; } // Find characters that occur in str2 but not in str1 std::vector<char> extra_chars; for (auto pair : count2) { char c = pair.first; int count = pair.second; if (count > count1) { extra_chars.push_back(c); } } return extra_chars;}int main() { std::string str1 = "abcd"; std::string str2 = "dabcdehi"; std::vector<char> extra_chars = find_extra_chars(str1, str2); // Print the extra characters found for (char c : extra_chars) { std::cout << c << " "; } std::cout << std::endl; return 0;} |
Java
import java.util.*;class GFG { public static List<Character> findExtraChars(String str1, String str2) { Map<Character, Integer> count1 = new HashMap<>(); Map<Character, Integer> count2 = new HashMap<>(); // Count occurrences of each character in str1 for (char c : str1.toCharArray()) { count1.put(c, count1.getOrDefault(c, 0) + 1); } // Count occurrences of each character in str2 for (char c : str2.toCharArray()) { count2.put(c, count2.getOrDefault(c, 0) + 1); } // Find characters that occur in str2 but not in str1 List<Character> extraChars = new ArrayList<>(); for (char c : count2.keySet()) { if (count2.get(c) > count1.getOrDefault(c, 0)) { extraChars.add(c); } } return extraChars; } public static void main(String[] args) { String str1 = "abcd"; String str2 = "dabcdehi"; List<Character> extraChars = findExtraChars(str1, str2); System.out.println(extraChars); // Output: [d, e, h, i] }}// This code is contributed by phasing17 |
Python3
def find_extra_chars(str1, str2): count1 = {} count2 = {} # Count occurrences of each character in str1 for c in str1: count1 = count1.get(c, 0) + 1 # Count occurrences of each character in str2 for c in str2: count2 = count2.get(c, 0) + 1 # Find characters that occur in str2 but not in str1 extra_chars = > count1.get(c, 0)] return extra_charsstr1 = "abcd"str2 = "dabcdehi"extra_chars = find_extra_chars(str1, str2)print(extra_chars) # Output: ['d', 'e', 'h', 'i']#This code is contributed by uomkar369 |
Javascript
function findExtraChars(str1, str2) { const count1 = new Map(); const count2 = new Map(); // Count occurrences of each character in str1 for (const c of str1) { count1.set(c, (count1.get(c) || 0) + 1); } // Count occurrences of each character in str2 for (const c of str2) { count2.set(c, (count2.get(c) || 0) + 1); } // Find characters that occur in str2 but not in str1 const extraChars = []; for (const of count2) { if (!count1.has(c) || count > count1.get(c)) { extraChars.push(c); } } return extraChars;}const str1 = 'abcd';const str2 = 'dabcdehi';const extraChars = findExtraChars(str1, str2);// Print the extra characters foundconsole.log(extraChars.join(' ')); |
C#
using System;using System.Collections.Generic;class Program { static List<char> FindExtraChars(string str1, string str2) { Dictionary<char, int> count1 = new Dictionary<char, int>(); Dictionary<char, int> count2 = new Dictionary<char, int>(); // Count occurrences of each character in str1 foreach (char c in str1) { if (count1.ContainsKey(c)) { count1++; } else { count1.Add(c, 1); } } // Count occurrences of each character in str2 foreach (char c in str2) { if (count2.ContainsKey(c)) { count2++; } else { count2.Add(c, 1); } } // Find characters that occur in str2 but not in str1 List<char> extra_chars = new List<char>(); foreach (KeyValuePair<char, int> pair in count2) { char c = pair.Key; int count = pair.Value; if (!count1.ContainsKey(c) || count > count1) { extra_chars.Add(c); } } return extra_chars; } static void Main(string[] args) { string str1 = "abcd"; string str2 = "dabcdehi"; List<char> extra_chars = FindExtraChars(str1, str2); // Print the extra characters found foreach (char c in extra_chars) { Console.Write(c + " "); } Console.WriteLine(); }} |
Output
['d', 'e', 'h', 'i']
The time complexity of this “dictionary-based” approach is O(n),
The auxiliary space complexity of this approach is O(n).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
