Solve sliding-window, flattening, decode, and O(1) random set

You are given four independent coding tasks. For each, describe your approach, time complexity, and handle edge cases. ## 1) Longest substring without repeating characters Given a string `s`, return the length of the longest contiguous substring that contains no repeated characters. - **Input:** `s` (may be empty) - **Output:** integer length - **Clarifications to handle:** - What should be returned for `s = ""`? - Character set assumptions (ASCII/Unicode) and implications - **Target complexity:** `O(n)` time ## 2) Flatten a linked list with `down` pointers You are given a linked structure where each node has two pointers: ```text class Node { int val; Node next; // next node in the same level Node down; // head of a sublist (may be null) } ``` Flatten the structure into a single-level list using only `next` pointers, in depth-first order: - For each node, its `down` list (recursively flattened) should appear immediately after the node, followed by the original `next` chain. - After flattening, all `down` pointers should be set to `null`. - **Input:** `head: Node` - **Output:** `head` of the flattened list - **Discuss:** recursive DFS vs iterative approach and stack-depth concerns ## 3) Lottery / raffle structure with O(1) delete Design an in-memory data structure that maintains a dynamic set of unique items and supports: - `insert(x)`: add item `x` if not present - `remove(x)`: delete item `x` if present - `getRandom()`: return a uniformly random item currently in the set - **Goal:** average `O(1)` time for all operations. - **Discuss:** why a plain list makes deletion `O(n)`, and how to achieve `O(1)` deletion. ## 4) Decode an encoded string with nesting Given an encoded string using the pattern `k[encoded_string]`, decode it. The encoding may be nested. Examples: - `"3[a]2[bc]" -> "aaabcbc"` - `"3[a2[c]]" -> "accaccacc"` - `"12[z]" -> "zzzzzzzzzzzz"` Rules/notes: - `k` is a positive integer and may have multiple digits. - Input is assumed valid. - **Discuss:** using a stack to handle nesting and efficient string concatenation.