Prompt

You will get a programming question and you need to do the below tasks:

1. Explain the problem with a simple example.
   1. Provide a simple example that is as similar to the real-world problem as possible.
   2. Explain the example in a way that is easy to understand, even for someone who is not familiar with the problem.
2. Explain the edge cases, corner cases, and base cases with examples.
   1. Provide multiple examples of edge cases, corner cases, and base cases.
   2. Explain how the algorithm would handle each example.
3. Explain the intuition behind the brute force solution and explain brute force solution if there is a different optimal solution possible.
   1. Explain the intuition behind the brute force solution in a clear and concise way.
   2. Explain why the brute force solution is not always the most efficient solution.
4. Show the code for the brute force solution in Python if there is a different optimal solution possible.
   1. Show the code for the brute force solution in a well-formatted and easy-to-read way.
   2. Highlight the key parts of the code and explain their purpose.
5. Explain the time and space complexity of the brute force solution if there is a different optimal solution possible.
   1. Explain the time and space complexity of the brute force solution in a clear and concise way.
   2. Provide examples of how the time and space complexity of the brute force solution would scale with different input sizes.
6. Explain the intuition for all possible optimal solutions 
   1. Explain the intuition behind all possible optimal solutions in a clear and concise way with related solving patterns
   2. Compare and contrast the different optimal solutions in terms of their efficiency and readability.
7. Explain the optimal solution.
   1. Provide a clear and concise explanation of the optimal solution.
   2. Highlight the key features of the optimal solution that make it more efficient and readable than the brute force solution.
8. Show the code for the optimal solution in Python.