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¶

```\$ cd path/to/cse-30872-fa21-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 challenge01               # Create and checkout challenge01 branch

\$ \$EDITOR challenge01/program.cpp           # Edit your code

\$ git commit -m "challenge01: done"         # Commit your changes

\$ git push -u origin challenge01            # Send changes to GitHub
```

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

```\$ .scripts/check.py
Checking challenge01 program.cpp ...
Result Success
Time 0.02
Score 6.00 / 6.00

\$ curl -F source=@challenge01/program.cpp https://dredd.h4x0r.space/code/cse-30872-fa21/challenge01
{"result": "Success", "score": 6, "time": 0.0016994476318359375, "value": 6, "status": 0}
```

Pull Request¶

Once you have committed your work and pushed it to GitHub, remember to create a pull request and assign it to the appropriate teaching assistant from the Reading 01 TA List.

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).