import collections
import unittest

# time: O(M + N) - space: O(N)
# def can_construct(ransom, magazine):
#     if not magazine: 
#         return False

#     ransom_dict = dict()

#     for s in ransom:
#         if s not in ransom_dict:
#             ransom_dict[s] = 1
#         else:
#             ransom_dict[s] += 1

#     for char in magazine:
#         if char in ransom_dict:
#             if ransom_dict[char] > 1:
#                 ransom_dict[char] -= 1
#             else:
#                 del ransom_dict[char]
    
#     return not ransom_dict

# def can_construct(ransom, magazine):
#     return all(ransom.count(x) <= magazine.count(x) for x in set(ransom))

#time: O(M+N) - space: O(M+N)
# each time a Counter is produced through an operation, any items with zero or negative counts are discarded
class Solution(object):
    def can_construct(self, ransom, magazine):
        return not collections.Counter(ransom) - collections.Counter(magazine)

class Test(unittest.TestCase):
    test_data = [('ab', 'aab', True), ('abb', 'aab', False)]

    def test_can_construct(self):
        solution = Solution()
        for data in self.test_data:
            actual = solution.can_construct(data[0], data[1])
            self.assertIs(actual, data[2])

if __name__ == '__main__':
    unittest.main()