Lexicographically Smallest Grid Path with One Letter Change
Updated
Problem statement
You are given a grid of lowercase letters with m rows and n columns. grid[i] is row i, and grid[i][j] is the letter in row i, column j.
You walk from the top-left cell (0, 0) to the bottom-right cell (m - 1, n - 1), moving only right or down. Write down the letters of the cells you visit, in order, including the first and last cell. This string always has m + n - 1 letters.
Before you start walking, you may change the letter of at most one cell of the grid to any lowercase letter.
Return the lexicographically smallest string you can write down.
Function
smallestPath(grid: String[]) → StringExamples
Example 1
grid = ["dbc","bab","cca"]return = "ababa"Every path starts at (0, 0), which holds d, so the best use of the change is to turn that cell into a. After that, both next cells hold b. The cell (1, 1) holds a and can be reached from either of them. From (1, 1) the next cells are (1, 2) with b and (2, 1) with c, so take b, and the walk ends at (2, 2) with a. The string is a b a b a, written ababa.
Example 2
grid = ["abz","zaa","bba"]return = "aaaaa"The path (0, 0) → (0, 1) → (1, 1) → (1, 2) → (2, 2) reads abaaa. Only one of its letters, the b at (0, 1), is not a. Change it to a and the string becomes aaaaa, which is the smallest possible.
Example 3
grid = ["xyz"]return = "ayz"There is only one path. Changing the first letter x to a gives ayz. Changing a later letter instead, such as z, gives xya, which is larger because it starts with x.
Constraints
m == grid.length,n == grid[i].length1 <= m, n <= 200grid[i]contains only lowercase English letters
More Infosys Online Assessment questions
- Lowest Common Ancestor with a Changing RootOA · Seen Nov 2026
- Minimum Leaf Path Sum over All RootsOA · Seen Nov 2026
- Split Array to Minimize the Largest SumOA · Seen Nov 2026
- Cherry PickupOA · Seen Nov 2026
- Minimum Cost to Supply Water with Wells and PipesOA · Seen Nov 2026
- Minimum Cost to Tile a Strip with Widths 1, 2, and 3OA · Seen Nov 2026
- Minimum Rounds to Complete All TasksOA · Seen Nov 2026
- Count Equal-Distinct Character PartitionsOA · Seen Oct 2026
- Maximum Alternating-Index Packet ValueOA · Seen Oct 2026
- Usable Water with Contaminated PillarsOA · Seen Oct 2026
Similar questions at other companies
- Get Minimum ErrorsAmazon · OA
- Maximize Beautiful SubstringsFortinet · OAFortinet interview questions
- Count Grid Words with One TurnCapital One · OACapital One interview questions
- Wildcard MatchingTripjack · ONSITE INTERVIEWTripjack interview questions
- Match a Pattern With ? and *Adobe · PHONE SCREENAdobe interview questions
- Most Relevant Text SpanHebbia · PHONE SCREEN
- Split Array Largest SumAuxoAI · OA
- Safest Shortest Path Through a GridSnowflake · OASnowflake interview questions
- Balance a Chemical EquationMicrosoft · OAMicrosoft interview questions
- Longest Repeated Letter Block with Adjacent SwapsIntuit · OAIntuit interview questions