Editors capitalise headlines with a special rule: every word is capitalised (first letter uppercase, the rest lowercase) except the small words a, an, and, as, at, but, by, for, in, of, on, or, the, to, which are written entirely in lowercase, unless the small word is the first or last word of the headline.
Write headline(s) that applies this rule. Words are separated by any amount of whitespace; the result uses single spaces and has no leading or trailing spaces.
Examples
Input: s = "the lord of the rings"
Output: "The Lord of the Rings"
Input: s = "a TALE OF two CITIES"
Output: "A Tale of Two Cities"
Input: s = "what to do"
Output: "What to Do"
Explanation: "do" is not a small word, and it is also the last word.
Constraints
0 <= len(s) <= 10**5, letters and whitespace only- Target: O(n) time
Goals
- Normalise whitespace with split and join
- Apply a rule that depends on a word's position
- Use a set for membership tests