Find common elements of two strings including characters that occur many times

Question

I would like to get common elements in two given strings such that duplicates will be taken care of. It means that if a letter occurs 3 times in the first string and 2 times in the second one, then in the common string it has to occur 2 times. The length of the two strings may be different. eg

s1 = 'aebcdee'
s2 = 'aaeedfskm' 
common = 'aeed'

I can not use the intersection between two sets. What would be the easiest way to find the result 'common' ? Thanks.

Answer 1

Well there are multiple ways in which you can get the desired result. For me the simplest algorithm to get the answer would be:

1. Define an empty dict. Like d = {}
2. Iterate through each character of the first string:
   if the character is not present in the dictionary, add the character to the dictionary.
   else increment the count of character in the dictionary.
3. Create a variable as common = ""
4. Iterate through the second string characters, if the count of that character in the dictionary above is greater than 0: decrement its value and add this character to common
5. Do whatever you want to do with the common

The complete code for this problem:

s1 = 'aebcdee'
s2 = 'aaeedfskm' 

d = {}

for c in s1:
    if c in d:
        d[c] += 1
    else:
        d[c] = 1

common = ""

for c in s2:
    if c in d and d[c] > 0:
        common += c
        d[c] -= 1

print(common)

Answer 2

You can use two arrays (length 26). One array is for the 1st string and 2nd array is for the second string.

Initialize both the arrays to 0.

The 1st array's 0th index denotes the number of "a" in 1st string, 1st index denotes number of "b" in 1st string, similarly till - 25th index denotes number of "z" in 1st string.

Similarly, you can create an array for the second string and store the count of each alphabet in their corresponding index.

s1 = 'aebcdee' s2 = 'aaeedfs' Below is the array example for the above s1 and s2 values

Now you can run through the 1st String s1 = 'aebcdee'

for each alphabet find the

K = minimum of ( [ count(alphabet) in Array 1 ], [ count(alphabet) in Array 2 ] ) and print that alphabet K times. then make that alphabet count to 0 in both the arrays. (Because if you dint make it zero, then our algo might print the same alphabet again if it comes in the future).

Complexity - O( length(S1) )

Note - You can also run through the string having a minimum length to reduce the complexity. In that case Complexity - O( minimum [ length(S1), length(S2) ] )

Please let me know if you want the implementation of this.