Largest number in one swap

JavaView on GFG

Time: O(n)

Space: O(n)

Problem Overview

Make the largest number by performing at most one swap of two digits.

Intuition

Make the largest number by performing at most one swap of two digits.

Algorithm

1From right to left: track the max digit seen so far and its position.
2From left to right: find first digit smaller than max digit to its right. Swap. Return result.

Common Pitfalls

• Same as LC 670. Scan right-to-left for max. Then left-to-right for first improvement opportunity.

Largest number in one swap.java

Java

// Approach: Find rightmost larger digit to swap with each digit from left. Pick the swap that maximizes result.
// Time: O(n) Space: O(n)
class Solution {
    public String largestSwap(String s) {
        char maxVal = '0';
        int valIdx = -1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c >= maxVal) {
                maxVal = c;
                valIdx = i;
            }
        }

        StringBuilder result = new StringBuilder(s);

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (i != valIdx && maxVal != c) {
                char d = result.charAt(i);
                result.setCharAt(i, maxVal);
                result.setCharAt(valIdx, d);
                break;
            }
        }

        return result.toString().compareTo(s) >= 0 ? result.toString() : s;
    }
}

// Version 2
class Solution1 {
    public String largestSwap(String s) {
        char[] c = s.toCharArray();

        char maxDigit = 0;
        int maxIdx = -1, l = -1, r = -1;

        for (int i = c.length - 1; i >= 0; i--) {
            if (c[i] > maxDigit) {
                maxDigit = c[i];
                maxIdx = i;
                continue;
            }
            if (c[i] < maxDigit) {
                l = i;
                r = maxIdx;
            }
        }

        if (l == -1)
            return s;

        char t = c[l];
        c[l] = c[r];
        c[r] = t;

        return new String(c);
    }
}

Was this solution helpful?