3970. Shortest Path With At Most K Consecutive Identical Characters

2026, Oct 29 3 mins read

1. Description

A directed weighted graph has n nodes numbered 0 through n - 1. Each entry edges[i] = [u$_i$, v$_i$, w$_i$] describes an edge from u$_i$ to v$_i$ with weight w$_i$.
The string labels assigns character labels[i] to node i.
Find the minimum total edge weight needed to reach node n - 1 from node 0, subject to every run of identical characters along the visited nodes having length at most k. Include both endpoints when forming the label sequence.
Return -1 if no valid path exists.

2. Example

Example 1

Input: n = 3, edges = [[0,1,1],[1,2,1],[0,2,3]], labels = “aab”, k = 1
Output: 3
Explanation: The direct edge from 0 to 2 gives labels “ab” and cost 3. Going through node 1 would produce the forbidden run “aa”.

Example 2

Input: n = 3, edges = [[0,1,1],[1,2,1],[0,2,3]], labels = “aab”, k = 2
Output: 2
Explanation: The route 0 → 1 → 2 costs 2. Its label sequence “aab” has no run longer than two characters.

Example 3

Input: n = 3, edges = [[0,1,1],[1,2,1]], labels = “aaa”, k = 2
Output: -1
Explanation: The only route has three consecutive ‘a’ labels, exceeding the limit of two.

3. Constraints

1 <= n == labels.length <= 5 * 10$^4$
0 <= edges.length <= 5 * 10$^4$
edges[i] == [u$_i$, v$_i$, w$_i$]
0 <= u$_i$, v$_i$ <= n - 1
u$_i$ != v$_i$
1 <= w$_i$ <= 10$^4$
labels contains only lowercase English letters.
1 <= k <= 50

4. Solutions

Dijkstra

n = number of nodes, m = edges.size()
Time complexity: O(nk + mk log(mk + 1))
Space complexity: O(nk + mk)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    int shortestPath(int n, vector<vector<int>> &edges, string labels, int k) {
        vector<vector<pair<int, int>>> graph(n);
        for (const auto &edge : edges) {
            int s = edge[0], t = edge[1], w = edge[2];
            graph[s].emplace_back(t, w);
        }

        vector<vector<int>> distances(n, vector<int>(k + 1, numeric_limits<int>::max()));
        distances[0][1] = 0;

        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
        pq.emplace(0, 0, 1);

        while (!pq.empty()) {
            const auto [cost, node, count] = pq.top();
            pq.pop();

            if (cost != distances[node][count]) {
                continue;
            }

            if (node == n - 1) {
                return cost;
            }

            for (auto [next_node, weight] : graph[node]) {
                int next_count = labels[node] == labels[next_node] ? count + 1 : 1;
                if (next_count > k) {
                    continue;
                }

                int next_cost = cost + weight;
                if (next_cost < distances[next_node][next_count]) {
                    distances[next_node][next_count] = next_cost;
                    pq.emplace(next_cost, next_node, next_count);
                }
            }
        }

        return -1;
    }
};

Search

Tags