After enjoying watching The Greatest Showman outside at the Movies on the Lawn in the Orange County Great Park a couple of years ago, the instructor's children asked to watch more musicals. Having grown up a huge Disney fan, the instructor's wife showed them the classic Mary Poppins.

In this musical, there is a song about the peculiar and ridiculous1 word Supercalifragilisticexpialidocious. The children thought this word was hilarious and asked Alexa to play the song over and over2. Eventually, they asked Alexa to spell the word, but the spy nanny digital assistant didn't understand their command, so the children (begrudgingly) resorted to asking their parents, who wrote down the word for them on some paper3.

Looking at the word on paper, the children realized they could form many smaller words from the letters in Supercalifragilisticexpialidocious. For instance, they could form the word is three times, ace twice, and rage once using the letters in Supercalifragilisticexpialidocious only up to the number times they occurred in the original word.

Knowing that their father has a bunch of students who do that computer programming thing, they asked him to request that you write a program that determines the number of times a word could be formed out of the letters of another word.

Input

The input will be a series of space-separated word pairs, s1 and s2, with one pair per line. Here is an example input:

supercalifragilisticexpialidocious is
supercalifragilisticexpialidocious ace
supercalifragilisticexpialidocious rage

Output

For each pair of words, your program is to determine how many times s2 can be formed using the letters in s1 (where each letter in s1 is only used up to the number of times it appears in s1) and print out that number.

Here is the output for the example input above:

3
2
1

Algorithmic Complexity

For each input test case, your solution should have the following targets:

Time Complexity O(S1 + S2), where S1 and S2 correspond to the lengths of each word in the input pair.
Space Complexity O(1)

Your solution may be below the targets, but it should not exceed them.

Submission

To submit your work, follow the same procedure you used for Reading 01:

$ cd path/to/cse-34872-su21-assignments     # Go to assignments repository
$ git checkout master                       # Make sure we are on master
$ git pull --rebase                         # Pull any changes from GitHub

$ git checkout -b challenge02               # Create and checkout challenge02 branch

$ $EDITOR challenge02/program.cpp           # Edit your code

$ git add challenge02/program.cpp           # Stage your changes
$ git commit -m "challenge02: done"         # Commit your changes

$ git push -u origin challenge02            # Send changes to GitHub

To check your code, you can use the .scripts/check.py script or curl:

$ .scripts/check.py
Checking challenge02 program.cpp ...
  Result Success
    Time 0.02
   Score 6.00 / 6.00

$ curl -F source=@challenge02/program.cpp https://dredd.h4x0r.space/code/cse-34872-su21/challenge02
{"result": "Success", "score": 6, "time": 0.0016994476318359375, "value": 6, "status": 0}

Pull Request

Once you have commited your work and pushed it to GitHub, remember to create a pull request and assign it to the teaching assistant.


  1. Quite atrocious; makes you sound precocious. 

  2. I hope the NSA likes Disney musicals. 

  3. After consulting the spellchecker in the cloud (ie. DuckDuckGo).