Find first 5-7-5 haiku in sentence

Question

Given a sentence containing mixed case and punctuation, and a syllable dictionary mapping lowercase words to their syllable counts, implement:

find_haiku(sentence: str, syllable_dict: dict) -> list[str] | None

Return the first contiguous three-line haiku whose three lines have 5, 7, and 5 syllables respectively, or None if no such haiku exists.

1. The three lines must be formed by partitioning a single contiguous subsequence of words into three consecutive segments that sum to 5, 7, and 5 syllables (in that order).
2. Treat tokens case-insensitively for dictionary lookups, and strip leading/trailing punctuation when matching keys.
3. When returning the three lines, preserve each original token's casing and punctuation (return the words exactly as they appeared in the sentence).
4. Aim for O(N) time (e.g., prefix sums + hashing) and state the space complexity.
5. Discuss edge cases such as: unknown words (not in the dictionary), apostrophes (e.g., "don't"), trailing punctuation, and multiple/irregular spaces.

Explain your approach and its time and space complexity.