Maximize number with one digit swap
Overview
This question evaluates a candidate's skill in digit and string manipulation, greedy algorithm design, and implementation of linear-time algorithms. It is commonly asked in the Coding & Algorithms domain to assess algorithmic efficiency, practical problem-solving with edge-case handling, and the application of greedy strategies as a practical algorithmic task rather than a purely conceptual exercise.
Given a non-negative integer n (as an int or string), perform at most one swap of two digits to produce the maximum possible value. Return the resulting integer. Design an O(L) algorithm (L = number of digits) using last-occurrence tracking of digits and scan from most significant to least significant. Include an early exit when the current digit is already the largest available to its right and no better swap exists.