LeetCode Daily #3962: 30 Oct 2026 | Shortest Path With At Most K Consecutive Identical Characters

Brute to Best: the LeetCode problem of the day, from the naive solution to the optimal one. In this video: The problem: each edge has a weight and a letter, and a valid path may never use the same letter more than k times in a row. Find the cheapest path from the source to the target Why plain Dijkstra breaks: the cheapest way to reach a node may arrive on a long run of one letter and be stuck there, while a slightly dearer arrival can continue. One distance per node is not enough information Brute force: DFS over every path while tracking the current run, which is exponential The key insight: the constraint is memory, so fold that memory into the state. A state is (node, last letter, current run length) Transition: taking an edge with the same letter sets run + 1 and is rejected once that exceeds k, while a different letter resets the run to 1 Run Dijkstra over the expanded graph with a priority queue keyed on total weight The state count is n × 26 × k, and each edge is relaxed once per incoming state, which keeps it tractable The answer is the smallest distance over all states sitting on the target node Dry run with k = 2: the three-a chain to node 3 is illegal, so the path detours through the b edge Complexity: O(E × 26 × k × log(n × 26 × k)) time and O(n × 26 × k) space Problem: https://leetcode.com/problems/shortes... Related: Cheapest Flights Within K Stops (787), Path With Minimum Effort (1631), Minimum Cost to Reach Destination in Time (1928) Full Daily Challenge playlist on the channel. Subscribe for a new LeetCode daily problem, solved from brute force to the best solution, every day. Hashtags #leetcode #leetcode3962 #leetcodedaily #potd #shortestpath #dijkstra #graph #statespace #priorityqueue #medium #coding #codinginterview #dsa #algorithms #brutetobest