Skip to content
Advertisement

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

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.

Advertisement

Answer

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)
User contributions licensed under: CC BY-SA
3 People found this is helpful
Advertisement