Alphabet Soup -Determine if you can write your message with the letters found in your bowl of soup

Question

I have been given a task to solve in python, need a help as I am not able to get an output, below is the question: -

Everyone loves alphabet soup. And of course, you want to know if you can construct a message from the letters found in your bowl.

Your Task:

Write a function that takes as input two strings:

The message you want to write
All the letters found in your bowl of alphabet soup

Assumptions:

It may be a very large bowl of soup containing many letters
There is no guarantee that each letter occurs a similar number of times - indeed some letters might be missing entirely
The letters are ordered randomly

The function should determine if you can write your message with the letters found in your bowl of soup. The function should return True or False accordingly.

Try to make your function efficient. Please use Big-O notation to explain how long it takes your function to run in terms of the length of your message (m) and the number of letters in your bowl of soup (s).

Below is the code I have tried but it is not working as per the task:-

def sol(alpha):
    srt = sorted(list(alpha))
    lwcase = sorted(list(alpha.lower()))
    upcase = []
    result = ''
    for i in srt:
        if i.isupper():
            upcase.append(i)

    for e in lwcase:
        if upcase.count(e.upper()) != 0:
            result += e.upper()
            upcase.pop(upcase.index(e.upper()))
        else:
            result += e
    return result

it = input("Enter a word please")
print(sol(it))

On phone right now, but here’s an idea: create a dict of letters in the soup to available frequencies (takes O(s)). Then iterate over your word and see if each letter’s frequency is zero (or if it’s not in the soup dict at all). If that’s true, return false. Otherwise, decrement the appropriate char’s available frequency count (O(m)). Total time is then O(m+s). Maybe there’s a more efficient implementation with a multiset structure or something, but this is a good start. — William Bradley, Jun 03 '21 at 13:59

Stef · Answer 1 · 2021-06-03T15:43:53.433

I assume your teacher expects you to write an algorithm for scratch on your own. However, knowing how to use the modules of the standard library is a pretty useful skill. Here is a solution using collections.Counter, which is a subclass of dict.

Code

import collections

def validate_soup(msg, soup):
  msg_preprocessed = ''.join(msg.lower().split())
  soup_preprocessed = ''.join(soup.lower().split())
  msg_count = collections.Counter(msg_preprocessed)
  soup_count = collections.Counter(soup_preprocessed)
  return all(n <= soup_count[k] for k,n in msg_count.items())

Tests

>>> validate_soup('Hello World', 'loollhed')
False
>>> validate_soup('Hello World', 'loollhedw')
False
>>> validate_soup('Hello World', 'loolhedwr')
False
>>> validate_soup('Hello World', 'loollhedwr')
True
>>> validate_soup('Hello World', 'abcloollhedwrdef')
True

Explanation

First, the processing step.

.lower() puts the message in lowercase, so that 'Hello World' and hello world are equivalent, see the documentation;
''.join(s.split()) removes all whitespace from a string s, see this question;
See also that question: Python: remove all non-alphabet chars from string?;

Then, the Counters:

collections.Counter(seq) produces a dictionary mapping the elements of seq to their number of occurrences, for instance Counter('helloworld') == {'l': 3, 'o': 2, 'h': 1, 'e': 1, 'w': 1, 'r': 1, 'd': 1};
all() is a builtin function to check that a predicates holds true for all elements of a sequence, see the doc;
all(n <= soup_count[k] for k,n in msg_count.items()) checks that the count n of every character k appearing in the message is lower than (or equal to) the count of character k in the soup.

score 0 · Accepted Answer · answered Jun 03 '21 at 14:20

Here’s my solution (see comment):

def validate_soup(s: str, chars: str)-> bool:
    d = {}
    for c in chars:
        count = d.get(c, 0)
        d[c] = count + 1
    for c in s:
        count = d.get(c, 0)
        if count <= 0:
            return False
        d[c] = count - 1
    return True