We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Strings
  4. Making Anagrams
  5. Discussions

Making Anagrams

  • geovanni_luna
     + 0 comments

    This python solution is O(n + m) time and O(k) space.

    O(k) because in the worse case all keys will will be unique and it will result in a space of O(n + m)

    def makingAnagrams(s1, s2):
    w1 = {}
    w2 = {}
    n = max(len(s1), len(s2))
    
    for i in range(n):
        if i < len(s1):
            if s1[i] not in w1:
                w1[s1[i]] = 0
            w1[s1[i]] += 1

        if i < len(s2):
            if s2[i] not in w2:
                w2[s2[i]] = 0
            w2[s2[i]] += 1
            
    all_keys = set(w1.keys()) | set(w2.keys())
    res = {}
    for key in all_keys:
        if key in w1 and key in w2:
            res[key] = abs(w1[key] - w2[key])
        elif key in w1:
            res[key] = w1[key]
        else:
            res[key] = w2[key]
            
    return sum(res.values())