3970. Shortest Path With At Most K Consecutive Identical Characters

  • Graph
  • String
  • Heap (Priority Queue)
  • Shortest Path
TIME
O(k (n + m) log(n k))
SPACE
O(n * k + m)
problem on leetcode ↗source on github ↗

Intuition

The labels along a path only matter through the length of the current run of identical characters. Moving along u -> v either extends the run (same label) or resets it to 1 (different label). So expand each node into states (node, run) with 1 <= run <= k, and run Dijkstra on that layered graph. That's at most n * k states, about 2.5 * 10^6.

A state with a shorter run is never worse than one with a longer run at the same node: every continuation that keeps the longer run within k also keeps the shorter one within k. Dijkstra pops states in order of distance, so once node u is settled with run r, any later pop of u with run >= r has both a larger distance and a worse run, and can be skipped.

Approach

  1. Build the adjacency list. For each edge, store whether both endpoints share a label.
  2. Keep dist over states node * (k + 1) + run, and best[u] = smallest run settled at u so far (starts at k + 1, meaning none).
  3. Start from (0, 1) with distance 0.
  4. Pop (d, u, r):
    • skip if stale (d > dist) or dominated (r >= best[u]);
    • otherwise set best[u] = r; if u == n - 1, return d, since the first pop of the target is the cheapest;
    • for each edge u -> v with weight w, the new run is r + 1 if the labels match, else 1. Skip if it exceeds k or is >= best[v]; relax as usual.
  5. If the heap empties, return -1.

Each node is settled at most k times, with strictly decreasing runs, and in practice usually once or twice.

Complexity

  • Time: O(k * (n + m) log(n * k)) in the worst case, where m = number of edges
  • Space: O(n * k + m)

Edge Cases

  • n == 1: the path is just node 0, one character, so the answer is 0
  • No edges, or n - 1 unreachable: -1
  • Every route to n - 1 passes through too many same-label nodes in a row: -1 (example 3)
  • Detours that break a run: a longer path through a node with a different label can be the only valid one, which is why the run is part of the state
  • Reaching a node again with a shorter run after a longer, cheaper visit: both are kept, since the shorter run may be the one that can continue
  • Path weights can exceed 32 bits in principle (a state path can be up to n * k edges long), so Java uses long distances

Code

from typing import List
import heapq


class Solution:
    def shortestPath(self, n: int, edges: List[List[int]], labels: str, k: int) -> int:
        """
        3970. Shortest Path With At Most K Consecutive Identical Characters
        Time: O(k * (n + m) log(n * k))
        Space: O(n * k + m)
        """
        adj = [[] for _ in range(n)]
        for u, v, w in edges:
            adj[u].append((v, w, labels[u] == labels[v]))

        # State id = node * K + run, where run is the length of the current
        # streak of identical labels ending at node (1..k).
        K = k + 1
        INF = float("inf")
        dist = [INF] * (n * K)
        # best[u] = smallest run already settled at u. A later pop of u with a
        # run at least that long is dominated: more distance, no better run.
        best = [K] * n

        dist[1] = 0
        heap = [(0, 1)]
        target = n - 1
        while heap:
            d, s = heapq.heappop(heap)
            if d > dist[s]:
                continue
            u, r = divmod(s, K)
            if r >= best[u]:
                continue
            best[u] = r
            if u == target:
                return d
            for v, w, same in adj[u]:
                nr = r + 1 if same else 1
                if nr > k or nr >= best[v]:
                    continue
                ns = v * K + nr
                nd = d + w
                if nd < dist[ns]:
                    dist[ns] = nd
                    heapq.heappush(heap, (nd, ns))

        return -1