Description
Shortest Path With At Most K Consecutive Identical Characters
MediumYou are given an integer n representing the number of nodes in a directed weighted graph, numbered from 0 to n - 1. This is represented by a 2D integer array edges, where edges[i] = [ui, vi, wi] represents a directed edge from node ui to node vi with weight wi.
You are also given a string labels of length n, where labels[i] is the character assigned to node i, and an integer k.
Return the minimum total edge weight of a path from node 0 to node n - 1 such that the concatenation of the labels of the nodes along the path contains at most k consecutive identical characters. If no valid path exists, return -1.
Example 1:
Input: n = 3, edges = [[0,1,1],[1,2,1],[0,2,3]], labels = "aab", k = 1
Output: 3
Explanation:
The optimal valid path from node 0 to node 2 is as follows:
- Use
edges[2] = [0, 2, 3]to reach node 2 with a weightwi = 3.
"ab", which satisfies at most k = 1 consecutive identical characters. Thus, the answer is 3.Example 2:
Input: n = 3, edges = [[0,1,1],[1,2,1],[0,2,3]], labels = "aab", k = 2
Output: 2
Explanation:
The optimal valid path from node 0 to node 2 is as follows:
- Use
edges[0] = [0, 1, 1]to reach node 1 with weightwi = 1. - Use
edges[1] = [1, 2, 1]to reach node 2 with weightwi = 1.
"aab", which satisfies at most k = 2 consecutive identical characters. Thus, the answer is 2.Example 3:
Input: n = 3, edges = [[0,1,1],[1,2,1]], labels = "aaa", k = 2
Output: -1
Explanation:
There is no valid path from node 0 to node 2 that satisfies at most k = 2 consecutive identical characters. Thus, the answer is -1.
Constraints:
1 <= n == labels.length <= 5 * 1040 <= edges.length <= 5 * 104edges[i] == [ui, vi, wi]0 <= ui, vi <= n - 1ui != vi1 <= wi <= 104labelsconsists of lowercase English letters1 <= k <= 50
Solutions
Gave up attempting to pass through a traditional path, brought in a priority queue version with some help from AI.
/**
* @param {number} n
* @param {number[][]} edges
* @param {string} labels
* @param {number} k
* @return {number}
*/
var shortestPath = function(n, edges, labels, k) {
const graph = Array.from({ length: n }, () => new Map());
for (const [u, v, w] of edges) {
graph[u].set(v, Math.min(graph[u].get(v) ?? Infinity, w));
}
const heap = new MinPriorityQueue(x => x[2]);
heap.enqueue([0, 1, 0]);
const dp = Array.from({ length: n }, () => Array(k + 1).fill(Infinity));
dp[0][1] = 0;
while (!heap.isEmpty()) {
const [node, count, total] = heap.dequeue();
if (total > dp[node][count]) continue;
if (node === n - 1) return total;
for (const [next, weight] of graph[node]) {
const nextCount = labels[node] === labels[next] ? count + 1 : 1;
if (nextCount > k) continue;
const nextTotal = total + weight;
if (nextTotal >= dp[next][nextCount]) continue;
dp[next][nextCount] = nextTotal;
heap.enqueue([next, nextCount, nextTotal]);
}
}
return -1;
};