Solve Sliding Window and Grid Search

In a Software Engineer phone screen, the candidate was asked to solve two coding problems. 1. **Longest substring with at most k distinct characters** Given a string `s` and an integer `k`, return the length of the longest contiguous substring that contains at most `k` distinct characters. Example: - Input: `s = "eceba"`, `k = 2` - Output: `3` 2. **Minimum-cost path in a grid with fuel and recharge cells** You are given an `m x n` grid with the following inputs: - `cost[i][j]`: the cost to enter cell `(i, j)` - `blocked[i][j]`: `true` if cell `(i, j)` cannot be entered - `recharge[i][j]`: `true` if entering cell `(i, j)` immediately refills your fuel back to `K` - `K`: the maximum fuel capacity Start at cell `(0, 0)` and reach cell `(m - 1, n - 1)`. Assume the start and destination cells are not blocked. Rules: - You may move one step at a time in the four cardinal directions: up, down, left, or right. - Each move consumes `1` unit of fuel. - You start with `K` units of fuel. - Every time you enter a cell, add that cell's `cost` to the total cost. The starting cell's cost must also be counted. - If you enter a recharge cell, your fuel is reset to `K` after the move. - Reaching the destination with exactly `0` fuel is allowed. Return the minimum total cost to reach the destination, or `-1` if it is impossible. **Follow-up:** If `K` is very large, how would you improve on an `O(m * n * K)` state-space solution?