A URL query string looks like q=hello+world&page=2&q=again. Write parse_query(qs) that returns a dictionary mapping each key to the list of its values in order of appearance.
Rules:
- Pairs are separated by
&; empty pairs are ignored. - A pair is split at its first
=. A pair without=has the value"". - Every
+in a key or value is replaced by a space. - No other decoding (such as
%20) is required.
Examples
Input: qs = "q=hello+world&page=2&q=again"
Output: {"q": ["hello world", "again"], "page": ["2"]}
Input: qs = "flag&x="
Output: {"flag": [""], "x": [""]}
Input: qs = ""
Output: {}
Constraints
0 <= len(qs) <= 10**5, printable ASCII without spaces- Target: O(n) time
Goals
- Split on nested separators in the right order
- Collect repeated keys into lists
- Apply a character substitution during parsing