BackTrackingProblem 13 of 19
Find Maximum number possible by doing at-most K swaps
Problem Statement
Given a positive integer, find the maximum number that can be formed by doing at-most K swap operations on its digits.
Example:
Input: num = "1234567", k = 4
Output: "7654321"
Input: num = "3435335", k = 3
Output: "5543333"
Input: num = "1234", k = 2
Output: "4231" (swap 1,4 -> "4231")
Explanation: Use at most k swaps to maximize the number.
Approach 1: Brute Force (Try All Swaps)
Intuition
At each position, try swapping with all positions to its right. Track the maximum number found across all valid swap sequences.
Algorithm
- For each position i, try swapping with each position j > i
- After each swap, recurse with k-1 swaps remaining
- Track maximum number found
- Backtrack after each swap
java
class Solution {
private String maxNum;
public void findMax(char[] num, int k) {
String current = new String(num);
if (current.compareTo(maxNum) > 0) {
maxNum = current;
}
if (k == 0) return;
int n = num.length;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
if (num[i] < num[j]) {
// Swap
char temp = num[i];
num[i] = num[j];
num[j] = temp;
findMax(num, k - 1);
// Backtrack
temp = num[i];
num[i] = num[j];
num[j] = temp;
}
}
}
}
public String findMaximumNum(String num, int k) {
maxNum = num;
findMax(num.toCharArray(), k);
return maxNum;
}
}Complexity Analysis
- Time Complexity: O(n! × k) - Try all swap combinations
- Space Complexity: O(n) - Recursion stack
Approach 2: Optimal (Greedy with Position Tracking)
Intuition
For each position from left, find the maximum digit to its right. If found, swap it to current position. This greedy approach combined with backtracking gives optimal result.
Algorithm
- For each position, find maximum digit in remaining positions
- Swap with rightmost occurrence of that maximum
- Recurse and backtrack
java
class Solution {
private String maxNum;
public void findMax(char[] num, int k, int index) {
if (k == 0 || index == num.length) {
return;
}
int n = num.length;
// Find maximum digit from index to end
char maxDigit = num[index];
for (int i = index + 1; i < n; i++) {
if (num[i] > maxDigit) {
maxDigit = num[i];
}
}
// If current digit is already maximum, move to next position
if (maxDigit == num[index]) {
findMax(num, k, index + 1);
return;
}
// Try swapping with all occurrences of maxDigit
for (int i = index + 1; i < n; i++) {
if (num[i] == maxDigit) {
// Swap
char temp = num[index];
num[index] = num[i];
num[i] = temp;
String current = new String(num);
if (current.compareTo(maxNum) > 0) {
maxNum = current;
}
findMax(num, k - 1, index + 1);
// Backtrack
temp = num[index];
num[index] = num[i];
num[i] = temp;
}
}
}
public String findMaximumNum(String num, int k) {
maxNum = num;
findMax(num.toCharArray(), k, 0);
return maxNum;
}
}Complexity Analysis
- Time Complexity: O(n! × k) in worst case, but much better in practice
- Space Complexity: O(n) - Recursion stack
Approach 3: Further Optimized (Skip Identical States)
Intuition
If current digit equals max digit, we don't need to swap. Also, try rightmost occurrence of max digit for potentially better results later.
java
class Solution {
private String maxNum;
private void solve(char[] num, int k, int index) {
String current = new String(num);
if (current.compareTo(maxNum) > 0) {
maxNum = current;
}
if (k == 0) return;
int n = num.length;
for (int i = index; i < n; i++) {
int maxIdx = i;
for (int j = i + 1; j < n; j++) {
if (num[j] >= num[maxIdx]) {
maxIdx = j;
}
}
if (num[maxIdx] > num[i]) {
char temp = num[i];
num[i] = num[maxIdx];
num[maxIdx] = temp;
solve(num, k - 1, i + 1);
temp = num[i];
num[i] = num[maxIdx];
num[maxIdx] = temp;
}
}
}
public String findMaximumNum(String num, int k) {
maxNum = num;
solve(num.toCharArray(), k, 0);
return maxNum;
}
}Complexity Analysis
- Time Complexity: O(n² × k) average case with optimizations
- Space Complexity: O(k) - Recursion depth limited by k
Key Takeaways
- Greedy Insight: Swap largest available digit to leftmost position
- Rightmost Selection: Choose rightmost occurrence for equal digits
- Backtracking: Essential since greedy alone doesn't always work
- Early Termination: Stop when no beneficial swaps exist
- State Tracking: Keep track of maximum found so far
- Position Progression: After placing digit at position i, focus on i+1