Largest number in K swaps

JavaView on GFG

Intuition

Greedy: find maximum digit in the remaining string, swap it to current position. Repeat for k swaps.

Algorithm

1For each position from left: find max digit in remaining str. If larger than current: swap, k--.
2If multiple max positions, swap rightmost to preserve future swaps.

Common Pitfalls

•Backtracking needed for optimal result. Greedy may not always be optimal without exhaustive search.

Largest number in K swaps.java

Java

// Approach: Greedy backtracking. At each position, find the max digit in remaining positions and swap it forward.
// Time: O(n! in worst) Space: O(n)
class Solution {
    // Function to find the largest number after k swaps.
    public String findMaximumNum(String str, int k) {
        char s[] = str.toCharArray();

        // Selection Sort
        for (int i = 0; i < s.length; i++) {
            if (k == 0)
                break;
            int max = i;
            for (int j = i + 1; j < s.length; j++) {
                if (s[max] <= s[j])
                    max = j;
            }

            if (s[max] == s[i])
                continue;
            else {
                swap(i, max, s);
                k--;
            }
        }

        return new String(s);
    }

    void swap(int i, int j, char s[]) {
        char t = s[i];
        s[i] = s[j];
        s[j] = t;
    }
}

Was this solution helpful?