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:

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.