Solve this leetcode-style coding problem using Python:

{{ problem_description }}

Before implementing, think through the requirements systematically:

STEP 1: BRAINSTORM APPROACHES
Consider multiple algorithmic approaches for solving this problem. Think about:
- What are 2-3 different ways to solve this problem?
- What are the time/space complexity trade-offs of each approach?
- Which approaches might be more robust for edge cases?

STEP 2: EVALUATE APPROACHES
For each approach you brainstormed:
- What are the potential pitfalls or edge cases that could cause failures?
- Which approach seems most likely to handle all test scenarios correctly?

STEP 3: SELECT BEST APPROACH
Choose the most promising approach and explain your reasoning briefly.

STEP 4: IMPLEMENT SOLUTION
Generate a Python solution that:
1. Solves the problem correctly using your selected approach
2. Handles all edge cases you identified
3. Uses clear variable names
4. Includes type hints
5. Has a comprehensive docstring

Return the complete solution code and the function name.

{% if evaluator_analysis %}
IMPORTANT: This is a REGENERATION ATTEMPT. The previous attempt failed.

ANALYSIS OF WHAT WENT WRONG:
{{ evaluator_analysis }}

INSTRUCTIONS FOR FIXING THE ISSUES:
{{ evaluator_instructions }}

PREVIOUS SOLUTION (learn from its mistakes):
{% if previous_solution_path %}
{{ read_file(previous_solution_path) }}
{% endif %}

{% if test_failure_context %}
SPECIFIC TEST FAILURES TO ADDRESS:
{{ test_failure_context }}
{% endif %}

Follow the evaluator instructions carefully to address the identified problems with the code. Start with the previous code and make the minimum changes necessary to address the failures.
{% endif %}
