Alphabet soup problem with best time complexity that is possible

user_7807893 0
Viewed 376

I got the below problem (alphabet soup) as my data structure course exercise.

https://github.com/kennedyCzar/AlphabetSoup-Using-Django

I solved it in O(m+s) where m is the length of the message and s is the length of the soup (I just created a table from the soup and decided if the message can be created or not using that table)

def checkBowl(message, soup):
  d = {}

  # O(S)
  for c in soup:
    d[c] = d.get(c, 0) + 1

  # O(m)
  for c in message:
    if(d.get(c, 0) == 0):
      return False
    else:
      d[c] -= 1

  # So the overall time complexity is O(m+s)
  return True

but it seems the given GitHub solved it in O(mlogm) however I think his/her solution is in O(m*s) cause he/she just didn't consider python's in operator works in O(length of the list).

By the way can someone please hint, is that possible to solve this problem with a better time complexity? (the problem specified that the bowl of soup may be very large)

data-structures algorithm python
2 Answers

As you stated, the linked algorithm, for each letter in the message, iterates over the soup to find the letter. If the letter is found, then it is removed from the soup. Hence the time complexity is O(m * S).

Your algorithm is O(m + S) because you iterate only once over the soup. So your solution is better.

But what if the soup is very large? What about an infinite soup? If the soup is an infinite generator, you will never finish to build your dictionary even if the first letters of the soup are the message itself.

This leads to an idea: why not iterate over the letters of the soup until you get the letters of the message? In this case, you'll read letters until you are able to write the message and stop as soon as the message is complete:

import collections

def check_bowl2(message, soup):
    # O(m)
    message_letters = collections.Counter(message)

    # O(S)
    for c in soup:
        if c not in message_letters: # we don't need `c`
            pass
        elif message_letters[c] == 1:
            del message_letters[c] # we won't need `c` anymore
            if not message_letters: # we found all letters
                return True
        else: # we still need `c`, but one less time
            message_letters[c] -= 1

    return False

The time complexity is still O(m + S), but the space complexity is reduced: O(m) versus O(S). Of course, if you are looking for many messages in the same soup, building the dict is still the best option.

I don't think you'll find an algorithm faster than O(S): in the worst case (the message is absent), you have to iterate over the whole soup at least once.

user_69144410

I don’t think you can go below linear with this problem, as it is not possible to check if a letter belongs to the alphabet soup without parsing it, and you obviously must parse your message.

BUT, your solution is only linear on AVERAGE as hash maps have a constant complexity on average only. So your worst case complexity is more like O(s^2+s.m).

You can improve it using your own data struct that do not rely on hash but binary trees for example, to achieve a worst case complexity of O(s.log(s)+ m.log(s)).

Edit : you also can exploit the fact that your characters are only ASCII ones.

def checkBowl(message, soup):                                                                                                                                                                            
  d = [0 for i in range(128)]
              
  # O(S)      
  for c in soup:
    d[ord(c)] +=1
              
  # O(m)      
  for c in message:
    if(d[ord(c)] == 0):
      return False
    else:     
      d[ord(c)] -= 1
               
  # So the overall time complexity is O(m+s)
  return True
user_115630400
Related