3970. Shortest Path With At Most K Consecutive Identical Characters
- Graph
- String
- Heap (Priority Queue)
- Shortest Path
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
- Build the adjacency list. For each edge, store whether both endpoints share a label.
- Keep
distover statesnode * (k + 1) + run, andbest[u]= smallest run settled atuso far (starts atk + 1, meaning none). - Start from
(0, 1)with distance 0. - Pop
(d, u, r):- skip if stale (
d > dist) or dominated (r >= best[u]); - otherwise set
best[u] = r; ifu == n - 1, returnd, since the first pop of the target is the cheapest; - for each edge
u -> vwith weightw, the new run isr + 1if the labels match, else1. Skip if it exceedskor is>= best[v]; relax as usual.
- skip if stale (
- 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 - 1unreachable:-1 - Every route to
n - 1passes 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 * kedges long), so Java useslongdistances
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 -1import java.util.*;
/**
* 3970. Shortest Path With At Most K Consecutive Identical Characters
* Time: O(k * (n + m) log(n * k))
* Space: O(n * k + m)
*/
class Solution {
public int shortestPath(int n, int[][] edges, String labels, int k) {
// Adjacency list in CSR form
int m = edges.length;
int[] start = new int[n + 1];
for (int[] e : edges) {
start[e[0] + 1]++;
}
for (int i = 0; i < n; i++) {
start[i + 1] += start[i];
}
int[] to = new int[m];
int[] wt = new int[m];
int[] fill = Arrays.copyOf(start, n);
for (int[] e : edges) {
int at = fill[e[0]]++;
to[at] = e[1];
wt[at] = e[2];
}
// State id = node * K + run, where run is the length of the current
// streak of identical labels ending at node (1..k).
int K = k + 1;
long[] dist = new long[n * K];
Arrays.fill(dist, Long.MAX_VALUE);
// 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.
int[] best = new int[n];
Arrays.fill(best, K);
PriorityQueue<long[]> heap = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
dist[1] = 0;
heap.add(new long[] {0, 1});
int target = n - 1;
while (!heap.isEmpty()) {
long[] top = heap.poll();
long d = top[0];
int s = (int) top[1];
if (d > dist[s]) {
continue;
}
int u = s / K, r = s % K;
if (r >= best[u]) {
continue;
}
best[u] = r;
if (u == target) {
return (int) d;
}
char cu = labels.charAt(u);
for (int j = start[u]; j < start[u + 1]; j++) {
int v = to[j];
int nr = labels.charAt(v) == cu ? r + 1 : 1;
if (nr > k || nr >= best[v]) {
continue;
}
int ns = v * K + nr;
long nd = d + wt[j];
if (nd < dist[ns]) {
dist[ns] = nd;
heap.add(new long[] {nd, ns});
}
}
}
return -1;
}
}