Shortest Path With At Most K Consecutive Identical Characters Python/Java solution

Implement BFS using a queue and store states like (node, lastChar, streak). When moving to a neighbor, update the streak depending on whether the character repeats or changes. Skip states where the streak exceeds K and maintain a visited structure keyed by node and streak information. The same pattern works in Python, Java, and C++.

What is the best approach for Shortest Path With At Most K Consecutive Identical Characters?

The most effective solution uses Breadth-First Search with an expanded state. Each state stores the node, the last character seen, and the current consecutive count. This allows the algorithm to enforce the K‑limit while still guaranteeing the shortest path property of BFS. The time complexity is typically O(V * K) because each node can appear with up to K consecutive states.

Is Shortest Path With At Most K Consecutive Identical Characters asked at Google/Amazon/Meta?

Variants of constrained shortest-path problems appear frequently in big tech interviews. Companies like Google, Amazon, and Meta often test BFS or graph traversal problems where additional state must be tracked, such as color constraints, step limits, or alternating patterns.

What data structure is used in Shortest Path With At Most K Consecutive Identical Characters?

The main data structure is a queue used for Breadth-First Search. A visited set or distance table tracks states that include the node, the last character, and the consecutive count. This prevents revisiting identical states and keeps the algorithm within O(V * K) complexity.

What is the time complexity of Shortest Path With At Most K Consecutive Identical Characters?

The optimal BFS solution runs in O(V * K + E * K) time, usually simplified to O(V * K) for sparse graphs. Each node may be visited with different streak lengths up to K. Space complexity is also O(V * K) due to the queue and visited-state tracking.

Description Hints 4 Solution Video 44:52

3970. Shortest Path With At Most K Consecutive Identical Characters

Q: Is Shortest Path With At Most K Consecutive Identical Characters easy or hard?

The problem is typically rated Medium because it combines standard BFS with additional state tracking. The graph traversal itself is straightforward, but recognizing that the state must include the consecutive character count makes it slightly more complex than a basic shortest-path problem.

Q: How to solve Shortest Path With At Most K Consecutive Identical Characters in O(n)?

Pure O(n) time is usually not possible because the algorithm must track different streak states up to K. The practical solution uses BFS with a state defined as (node, lastChar, streakLength). By pruning states that exceed K or were already visited, the search remains efficient and runs in O(V * K).

Medium44.7% acceptance

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] = [u_i, v_i, w_i] represents a directed edge from node u_i to node v_i with weight w_i.

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 weight w_i = 3.

The corresponding concatenation of labels is "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 weight w_i = 1.
Use edges[1] = [1, 2, 1] to reach node 2 with weight w_i = 1.

The corresponding concatenation of labels is "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 * 10⁴
0 <= edges.length <= 5 * 10⁴
edges[i] == [u_i, v_i, w_i]
0 <= u_i, v_i <= n - 1
u_i != v_i
1 <= w_i <= 10⁴
labels consists of lowercase English letters
1 <= k <= 50

Topics

Graph Heap (Priority Queue)Shortest Path String

Hints open one at a time

Hint 1

The validity of a path depends not only on the current node, but also on how many consecutive times the current node’s label has appeared at the end of the path.

Hint 2

Use Dijkstra on states (node, count), where count is the current consecutive run length of labels[node].

Hint 3

When moving from node u to node v, the next count becomes count + 1 if labels[u] == labels[v], otherwise it becomes 1. Ignore transitions where the next count exceeds k.

Hint 4

The answer is the minimum distance among all states ending at node n - 1.

44:52

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def shortestPath(self, n: int, edges: List[List[int]], labels: str, k: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

3
[[0,1,1],[1,2,1],[0,2,3]]
"aab"
1

Input

3
[[0,1,1],[1,2,1],[0,2,3]]
"aab"
2

Input

3
[[0,1,1],[1,2,1]]
"aaa"
2

Your code is saved on this device.Solution