You 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:
edges[2] = [0, 2, 3] to reach node 2 with a weight wi = 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:
edges[0] = [0, 1, 1] to reach node 1 with weight wi = 1.edges[1] = [1, 2, 1] to reach node 2 with weight wi = 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 <= 104labels consists of lowercase English letters1 <= k <= 50Problem Overview: You need the shortest path between two nodes (or grid cells) while enforcing a constraint: the path cannot contain more than K consecutive identical characters. Each step extends the path, but if the same character repeats more than K times in a row, that path becomes invalid.
Approach 1: Brute Force DFS with Backtracking (Exponential Time, O(V) Space)
The most direct idea is to explore every possible path using depth-first search. Track the current character and how many times it has appeared consecutively. Each recursive call checks whether the next node continues the same character streak or resets the counter. If the streak exceeds K, the branch stops. This works for small graphs but quickly becomes impractical because the number of paths grows exponentially. Time complexity is roughly O(2^V) in dense graphs, with O(V) recursion stack space. This approach mainly helps you reason about the constraint before optimizing.
Approach 2: BFS with State Expansion (O(V * K) Time, O(V * K) Space)
The shortest path requirement strongly suggests Breadth-First Search. Instead of storing just the node in the queue, store an expanded state: (node, lastChar, streakLength). When exploring neighbors, update the streak length. If the next character matches lastChar, increment the streak; otherwise reset it to 1. Skip transitions where the streak exceeds K. A visited structure must include both the node and streak information, otherwise valid states may be incorrectly pruned. Because each node can appear with at most K streak lengths, the complexity becomes O(V * K + E * K), commonly simplified to O(V * K). Space complexity is also O(V * K) for the queue and visited set.
Approach 3: BFS with Distance + State Compression (O(V * K) Time, O(V * K) Space)
A more practical variant stores distances in a 3D structure like dist[node][char][streak] or compresses it to track the best streak seen for each node and character. The queue still performs standard BFS, but transitions are skipped if a better or equal state was already processed. This reduces redundant exploration in graphs with many repeated characters. Conceptually, it combines shortest path traversal with a lightweight form of state-based dynamic programming.
Recommended for interviews: BFS with state expansion. Interviewers expect you to recognize that shortest path problems with extra constraints require expanding the state space. Starting with brute force demonstrates understanding of the rule, but the BFS formulation shows stronger algorithmic intuition and familiarity with constrained shortest-path patterns.
Solutions for this problem are being prepared.
Try solving it yourself| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS Brute Force | O(2^V) | O(V) | Small graphs or conceptual explanation of the constraint |
| BFS with State (node, char, streak) | O(V * K) | O(V * K) | General solution for shortest path with consecutive-character constraint |
| Optimized BFS with Distance Tracking | O(V * K) | O(V * K) | Large graphs where pruning repeated states improves performance |
Practice Shortest Path With At Most K Consecutive Identical Characters with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor