Solve common string/DP/stack problems

You are given four independent coding tasks. For each task, describe your approach and analyze time and space complexity. ## Task 1: Longest substring with all distinct characters **Input:** A string `s` (ASCII or lowercase letters). **Output:** An integer = the maximum length of a contiguous substring of `s` that contains no repeated characters. **Example:** `s = "abcabcbb"` → output `3` (e.g., "abc"). **Constraints (typical):** `0 ≤ |s| ≤ 2e5`. --- ## Task 2: Largest rectangle in a histogram **Input:** An array `heights` of length `n`, where `heights[i]` is the height of the `i`-th bar in a histogram. Each bar has width `1`. **Output:** The maximum area of any axis-aligned rectangle that can be formed using one or more contiguous bars. **Example:** `heights = [2,1,5,6,2,3]` → output `10` (bars 5 and 6). **Constraints (typical):** `1 ≤ n ≤ 2e5`, `0 ≤ heights[i] ≤ 1e9`. --- ## Task 3: Minimum cost to reach the last index with 1–2 steps You start at index `0`. From index `i`, you may move to `i+1` or `i+2` (if within bounds). Visiting an index `i` incurs `cost[i]` (including index `0` and the last index). **Input:** Arrays `cost` (or `nums` + per-position `cost`) of length `n`. **Output:** The minimum total cost to reach index `n-1`. **Example:** `cost = [1,100,1,1,1,100,1,1,100,1]` → output `6`. **Constraints (typical):** `1 ≤ n ≤ 2e5`, `0 ≤ cost[i] ≤ 1e9`. --- ## Task 4: Longest palindromic substring **Input:** A string `s`. **Output:** A substring of `s` that is a palindrome and has maximum possible length. If multiple answers exist, return any one. **Example:** `s = "babad"` → output `"bab"` (or `"aba"`). **Constraints (typical):** `1 ≤ |s| ≤ 2e3` (or specify if larger and discuss tradeoffs).