Reverse Words in a String (with extra constraints)

Coding: Reverse Words in a String (with extra constraints) You are given a string s consisting of English words and spaces. Reverse the order of the words in s. A word is a maximal substring consisting of non-space characters. s may contain: leading/trailing spaces multiple consecutive spaces Task 1 (Basic) Return a new string where the word order is reversed, and: words are separated by a single space the result contains no leading or trailing spaces Task 2 (Interview follow-up: keep spaces unchanged) After finishing Task 1, add an extra requirement: reverse the word order keep the number of spaces and the spacing pattern unchanged (i.e., every run of consecutive spaces stays the same length and remains in the same relative position; only the words are filled back in reversed order). Equivalently: split s into alternating word-runs and space-runs; keep all space-runs as-is, but place the word-runs back in reversed order. Constraints 1 <= len(s) <= 1e5 s contains printable ASCII characters (at least letters and spaces) Requirements Provide time and space complexity analysis Optimize for linear time if possible Sample tests (5) Input: "the sky is blue" Output (Task 1): "blue is sky the" Output (Task 2): "blue is sky the" Input: " hello world " Output (Task 1): "world hello" Output (Task 2): " world hello " Input: "a good example" Output (Task 1): "example good a" Output (Task 2): "example good a" Input: "single" Output (Task 1): "single" Output (Task 2): "single" Input: " a b c " Output (Task 1): "c b a" Output (Task 2): " c b a " Example Input the sky is blue Output blue is sky the blue is sky the