Skip to main content
Talentd

Shortest Path With At Most K Consecutive Identical Characters - Solution & Explanation

MediumStringGraphHeap (Priority Queue)Shortest Path4 min read
Practice this problem

Problem Statement

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:

  • Use edges[2] = [0, 2, 3] to reach node 2 with a weight wi = 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 wi = 1.
  • Use edges[1] = [1, 2, 1] to reach node 2 with weight wi = 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 * 104
  • 0 <= edges.length <= 5 * 104
  • edges[i] == [ui, vi, wi]
  • 0 <= ui, vi <= n - 1
  • ui != vi
  • 1 <= wi <= 104
  • labels consists of lowercase English letters
  • 1 <= k <= 50

Approach Overview

Problem 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

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS Brute ForceO(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 TrackingO(V * K)O(V * K)Large graphs where pruning repeated states improves performance

Video Solution

Leetcode Weekly Contest 507 | Q3 - Shortest Path With At Most K Consecutive | 3970 • DSA with Kumar K • 774 views views

Watch 6 more video solutions →

Frequently Asked Questions

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.
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++.
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).
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.

Ready to solve this problem?

Practice Shortest Path With At Most K Consecutive Identical Characters with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring