Frontend School

Lexicographically Smallest Path in a Grid with Restricted Character Usage

DSA
hard

Lexicographically Smallest Path in a Grid with Restricted Character Usage

Hard
Backtracking
Grid
String
Lexicographical

Overview

In a system that generates unique identifiers or codes, we often encounter scenarios where these codes are derived from traversing a structured data grid. For instance, imagine a configuration matrix for a complex software system, where paths through the matrix define specific feature sets or product versions. To optimize storage, indexing, or user experience, we need to find the 'best' possible code, often defined as the lexicographically smallest one. However, some characters in the grid might represent rare or expensive resources, and their usage must be strictly limited to control costs or maintain system stability. This problem challenges you to find such an optimal code under these critical constraints.

What you need to do / Task

  1. Implement a function findLexicographicalPath that takes a grid (2D array of characters) and an integer k.
  2. Find a path from the top-left cell (0, 0) to the bottom-right cell (R-1, C-1).
  3. You can only move right (row, col + 1) or down (row + 1, col).
  4. The string formed by concatenating characters along the path must be lexicographically the smallest among all valid paths.
  5. A path is considered valid if the total count of a specific restricted character (let's say 'X') in the path does not exceed k.
  6. If no such valid path exists, return an empty string.

Input & output

  • grid: A string[][] representing the character grid. Each cell contains a single uppercase English letter.
  • k: An integer representing the maximum allowed occurrences of the restricted character 'X' in the path.
  • Returns: A string representing the lexicographically smallest path. Returns "" if no such path exists.

Clarifications

  • The grid will always be non-empty, with R, C >= 1.
  • The character 'X' is case-sensitive, meaning 'x' would not count towards the k limit (though constraints say uppercase).
  • If multiple paths result in the same lexicographically smallest string, any one of them is acceptable (but due to the nature of lexicographical search, we'll naturally find the first one).

Examples

1

Example 1

Input:

grid = [["A","B"],["X","D"]], k = 0

Output:

"ABD"

Note:

The path 'ABD' (A->B->D) uses 0 'X's, which satisfies k=0. The other path 'AXD' (A->X->D) uses 1 'X', exceeding k=0. Thus, 'ABD' is the only valid path and therefore the lexicographically smallest.

2

Example 2

Input:

grid = [["A","X","B"],["C","D","X"]], k = 1

Output:

"ACDX"

Note:

Path length is R+C-1 = 2+3-1 = 4. Possible valid paths respecting k=1:

  1. A->C->D->X: Forms "ACDX". Uses 1 'X'. Valid.
  2. A->X->D (invalid path, ends at (1,1), not (1,2))
  3. A->X->B (invalid path, ends at (0,2), not (1,2))
  4. A->B->X (invalid path, ends at (0,2), not (1,2)) Since "ACDX" is the only valid path starting with 'A' and respecting k, it is the lexicographically smallest.
3

Example 3

Input:

grid = [["X","Y"],["Z","W"]], k = 0

Output:

""

Note:

All possible paths from (0,0) to (1,1) must start with 'X' at (0,0), immediately violating the k=0 constraint. Therefore, no valid path exists.

Constraints

Constraints & assumptions

  • 1 <= grid.length (R) <= 15
  • 1 <= grid[0].length (C) <= 15
  • grid[i][j] will be an uppercase English letter ('A' through 'Z').
  • 0 <= k <= R * C

What interviewers evaluate

  • Algorithmic Correctness: The solution must correctly identify the lexicographically smallest path while adhering to all movement and character usage rules.
  • Backtracking Efficiency: Demonstrates effective pruning strategies (e.g., based on lexicographical order and k constraint) to avoid redundant computations, crucial for a hard problem.
  • State Management: Manages recursive state (current position, path string, character count) accurately and cleanly.
  • Edge Case Handling: Properly handles scenarios such as k=0, k being very large, or when no valid path exists.

Loading editor...