Reason About Character Paths in a Grid

Problem Statement

You are given an m x n grid of lowercase English characters, a starting cell coordinate (start_row, start_col), and a positive integer k.

A valid path starts at (start_row, start_col) and moves to 4-directionally adjacent cells (up, down, left, or right). A single path cannot visit the same grid cell more than once (no cycles). As you traverse the grid, concatenate each visited cell's character to form a string.

Write a function to find all distinct strings of length k that can be formed along valid paths starting at (start_row, start_col). The returned list must be sorted in lexicographical order.

Function Signature

def find_character_paths(grid: list[list[str]], start_row: int, start_col: int, k: int) -> list[str]:
    pass

Input and Output Format

• Input:
  • grid: A 2D list of single-character strings (m x n).
  • start_row: An integer representing the starting row index (0 <= start_row < m).
  • start_col: An integer representing the starting column index (0 <= start_col < n).
  • k: An integer representing the required path length in terms of characters visited.
• Output: A list of strings of length k, sorted in ascending lexicographical order, with no duplicates.

Constraints

• 1 <= m, n <= 8
• 1 <= k <= min(10, m * n)
• grid[i][j] is a lowercase English letter ('a' - 'z').
• 0 <= start_row < m
• 0 <= start_col < n

Examples

Example 1

Input:
grid = [
    ['a', 'b', 'c'],
    ['d', 'e', 'f'],
    ['g', 'h', 'i']
]
start_row = 1
start_col = 1
k = 3

Output: ["eba", "ebc", "ede", "edg", "efc", "efi", "eha", "ehg", "ehi"]
# Note: "ede" is invalid because 'd' and 'e' would require revisiting (1, 1).
# Actual valid unique strings of length 3 from 'e' (1,1):
# e -> b -> a ("eba"), e -> b -> c ("ebc")
# e -> d -> a ("eda"), e -> d -> g ("edg")
# e -> f -> c ("efc"), e -> f -> i ("efi")
# e -> h -> g ("ehg"), e -> h -> i ("ehi")

Output:

["eba", "ebc", "eda", "edg", "efc", "efi", "ehg", "ehi"]

Example 2

Input:
grid = [
    ['x', 'y'],
    ['y', 'x']
]
start_row = 0
start_col = 0
k = 4

Output: ["xyxy"]
Explanation:
Path 1: (0,0) -> (0,1) -> (1,1) -> (1,0) produces "xyxx" -> wait, grid[1][1]='x', grid[1][0]='y', so 'x' -> 'y' -> 'x' -> 'y' = "xyxy".
Path 2: (0,0) -> (1,0) -> (1,1) -> (0,1) produces 'x' -> 'y' -> 'x' -> 'y' = "xyxy".
Both paths produce "xyxy", so only one distinct string is returned.

Edge Cases

• k = 1: The path consists only of the starting cell; return [grid[start_row][start_col]].
• k > m * n: No simple path can visit more cells than exist in the grid; return an empty list [].
• Dead ends: A branch may run out of unvisited neighbors before reaching length k; it should terminate without contributing to the output.