A few years ago, the instructor engaged1 in some biohacking. This means that he avoided eating things like grains and dairy when possible, and instead ate a lot of meats, fruits, and vegetables.

Because eating apples everyday is pretty boring, the instructor created a script that generates a sequence of fruits to eat (one per day). For example:

``````banana tangerine banana peach peach banana
``````

This means that on the first day, he will eat a `banana` and on the second day he will eat a `tangerine` and so on and so forth.

Since this script uses a random number generate to select the sequence of fruits, there are sometimes duplicates in his fruit eating schedule. This can be unfortunate, because the instructor doesn't want to eat the same thing everyday 2.

Given a sequence of fruits, the instructor wants to know what it is the length of longest subsequence of days with distinct fruits (and what fruits are in that subsequence).

For instance, in the example above, the longest sequence of days with distinct fruits is `tangerine banana peach` and so the length is `3`.

## Input¶

You will be given a series of fruit sequences, one sequence per line. Each line will contain a sequence of fruits separate by spaces as show below:

### Example Input¶

``````pineapple
orange grape
grape coconut pear
peach pineapple peach peach
grape apple banana peach pineapple
banana tangerine banana peach peach banana
apple grape tangerine coconut apple coconut grape
apple grape banana tangerine pineapple pear orange banana
pineapple apple coconut apple pineapple banana pineapple orange coconut
``````

## Output¶

For each sequence of fruits, you are to report the longest sequence of distinct fruits as show below:

### Example Output¶

``````1: pineapple
2: orange, grape
3: grape, coconut, pear
2: peach, pineapple
5: grape, apple, banana, peach, pineapple
3: tangerine, banana, peach
4: apple, grape, tangerine, coconut
7: apple, grape, banana, tangerine, pineapple, pear, orange
4: coconut, apple, pineapple, banana
``````

Note, you should display the length of the subsequence, followed by the fruits, separated by `", "`. If there are multiple subsequences with the maximum length, choose the first subsequence. Make sure there is no trailing space.

#### Programming Challenges¶

This problem is inspired by "Problem 13.11" in Elements of Programming Interviews.

#### Algorithmic Complexity¶

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

 Time Complexity `O(N)`, where `N` is the length of each input sequence. Space Complexity `O(N)`, where `N` is the length of each input sequence.

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

## Submission¶

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

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

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

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

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

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

\$ curl -F source=@challenge06/program.cpp https://dredd.h4x0r.space/code/cse-30872-fa22/challenge06
{"result": "Success", "score": 6, "time": 0.016405344009399414, "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 03 TA List.

1. Notice the past tense.

2. Actually not true. I do eat basically the same thing everyday...