FastPrepLexicographically Smallest Grid Path with One Letter Change
Problems/Lexicographically Smallest Grid Path with One Letter Change

Lexicographically Smallest Grid Path with One Letter Change

Infosys logoInfosys● HardFULLTIMEOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in an Infosys full-time online assessment. The third of four coding questions was a grid dynamic programming task about the smallest path in dictionary order, with one slip allowed.

Only that title was shared. It does not say what a slip is, how you may move, or what the grid holds. Here the grid holds letters, you move right or down, the path spells a string, and the one slip is a single cell whose letter you may change before walking.

Our version is about 40% the same as the reported question.

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[]) → String

Examples

Example 1

grid = ["dbc","bab","cca"]return = "ababa"
grid
0120dbc1bab2cca

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"
grid
0120abz1zaa2bba

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"
grid
0120xyz

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].length
  • 1 <= m, n <= 200
  • grid[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
All Infosys interview questionsSee Infosys hiring insights
Saved
class Solution {
    public String smallestPath(String[] grid) {
        // Write your code here.
    }
}
Checking account…