Log inSign up
hardGeeksforGeeksNot Started

Maximum Number by K Swaps

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Backtracking
Solve on GeeksforGeeks
Lesson

Problem Statement

Given a positive integer N represented as a string s and an integer k, find the maximum possible number that can be created by doing at most k swap operations of digits.

Return the maximum number as a string.

Example 1 · K = 4 Swaps with 254:

Input: s = "254", k = 1
Output: "524"
Explanation: Swap 2 with 5 at index 0 to get 524.

Example 2 · K = 4 Swaps with 1234567:

Input: s = "1234567", k = 4
Output: "7654321"
Explanation: After 4 swaps: 7234561 -> 7634521 -> 7654321 -> 7654321.

Example 3 · K = 2 Swaps with 7599:

Input: s = "7599", k = 2
Output: "9975"
Explanation: Swap 7 with 9 (at index 3) -> 9597, then swap 5 with 9 -> 9957, or directly 9975.

Constraints:

  • 1 <= s.length <= 15
  • 1 <= k <= 10
  • s consists of only digits 0 through 9.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why a purely greedy swap fails when multiple identical maximum digits exist.
  • Master state-restoring backtracking with string swap unwinding.
  • Optimize branch pruning by identifying suffix maxima.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Maximize a string number using at most k swaps
  • Greedy choice alone fails due to duplicate maximum digits in suffix
  • Backtracking required to explore which identical max digit yields better downstream swaps

Algorithmic Decision Tree:

  • Scan suffix s[i + 1..n - 1] for the largest character maxChar.
  • If maxChar > s[i], iterate j from i + 1 to n - 1: if s[j] == maxChar, swap s[i] with s[j], update max, recurse with k - 1, and backtrack.
  • Always explore next index i + 1 even if no swap occurs at index i.

Connected Patterns:

Next PermutationLargest NumberPermutations

1. All-Pairs Swap Backtracking (O(N^(2K)))

Intuition

Iterate over all pairs (i, j) where i < j. If s[i] < s[j], swap them, compare with max, recurse with k - 1, and backtrack.

When to apply: Simple baseline to show complete exploration of swap space.

Algorithm

  1. If k == 0, return.
  2. Loop i from 0 to n - 2:
  3. - Loop j from i + 1 to n - 1:
  4. - If s[i] < s[j]:
  5. - Swap s[i] and s[j].
  6. - If s > maxStr, maxStr = s.
  7. - Recurse solve(s, k - 1).
  8. - Swap back s[i] and s[j].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 void solve(string& s, int k, string& maxStr) {
9 if (k == 0) return;
10 int n = s.length();
11
12 for (int i = 0; i < n - 1; i++) {
13 for (int j = i + 1; j < n; j++) {
14 if (s[i] < s[j]) {
15 swap(s[i], s[j]);
16 if (s > maxStr) maxStr = s;
17 solve(s, k - 1, maxStr);
18 swap(s[i], s[j]); // backtrack
19 }
20 }
21 }
22 }
23
24public:
25 string findMaximumNum(string s, int k) {
26 string maxStr = s;
27 solve(s, k, maxStr);
28 return maxStr;
29 }
30};
31
32int main() {
33 Solution sol;
34 cout << sol.findMaximumNum("7599", 2) << endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(N^(2K)) — There are O(N2) pairs to swap at each of the K recursive levels.
  • Space complexity: O(K) — Recursion depth is K.

2. Index-Guided Backtracking (Left-to-Right)

Intuition

Maintain index pointer idx. Find if there is any j > idx such that s[j] > s[idx]. If found, swap and recurse on idx + 1 with k - 1. Also branch to idx + 1 without swapping.

When to apply: Intermediate approach avoiding redundant swaps in already processed prefixes.

Algorithm

  1. In solve(idx, k):
  2. - If k == 0 || idx == n - 1: return.
  3. - For j from idx + 1 to n - 1:
  4. - If s[j] > s[idx]:
  5. - Swap, update maxStr, recurse solve(idx + 1, k - 1), swap back.
  6. - Recurse solve(idx + 1, k).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 void solve(string& s, int idx, int k, string& maxStr) {
9 if (k == 0 || idx == s.length() - 1) return;
10 int n = s.length();
11
12 for (int j = idx + 1; j < n; j++) {
13 if (s[j] > s[idx]) {
14 swap(s[idx], s[j]);
15 if (s > maxStr) maxStr = s;
16 solve(s, idx + 1, k - 1, maxStr);
17 swap(s[idx], s[j]);
18 }
19 }
20 solve(s, idx + 1, k, maxStr);
21 }
22
23public:
24 string findMaximumNum(string s, int k) {
25 string maxStr = s;
26 solve(s, 0, k, maxStr);
27 return maxStr;
28 }
29};
30
31int main() {
32 Solution sol;
33 cout << sol.findMaximumNum("7599", 2) << endl;
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(N^K) — Branches only at positions where suffix has larger digits.
  • Space complexity: O(N) — Call stack depth is N.

3. Suffix Maximum Only Swapping (Optimal)

Intuition

At position idx, find maxChar = max(s[idx+1..n-1]). If maxChar <= s[idx], no swap can improve position idx, so simply recurse on idx + 1 without decrementing k. If maxChar > s[idx], only swap with indices j where s[j] == maxChar, completely ignoring smaller digits. This drastically cuts the branching factor.

When to apply: The gold standard optimal solution with maximum branch pruning.

Algorithm

  1. In solve(idx, k):
  2. - If k == 0 || idx == n - 1: return.
  3. - Find maxChar = max(s[idx..n - 1]).
  4. - If maxChar != s[idx]: k-- (a swap is mandatory for this index).
  5. - Loop j from n - 1 down to idx:
  6. - If s[j] == maxChar:
  7. - Swap s[idx] and s[j].
  8. - If s > maxStr, update maxStr = s.
  9. - Recurse solve(idx + 1, k).
  10. - Swap back.

Suffix Max Swap Trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Step 0: Initial string s = '7599', idx = 0, k = 2
Visual state
Values and pointers at this exact step
array
S
7
5
9
9
0
1
2
3
Variables at this step
maxChar
9
swapIndex
0
kLeft
2
Why this step matters

Step 0: Initial string s = '7599', idx = 0, k = 2. Max in s[0..3] is 9.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 void solve(string& s, int idx, int k, string& maxStr) {
9 if (k == 0 || idx == s.length() - 1) return;
10 int n = s.length();
11
12 char maxChar = s[idx];
13 for (int j = idx + 1; j < n; j++) {
14 if (s[j] > maxChar) maxChar = s[j];
15 }
16
17 // If s[idx] is already the maximum, no swap needed at this index
18 if (maxChar != s[idx]) {
19 k--;
20 }
21
22 for (int j = n - 1; j >= idx; j--) {
23 if (s[j] == maxChar) {
24 swap(s[idx], s[j]);
25 if (s > maxStr) maxStr = s;
26 solve(s, idx + 1, k, maxStr);
27 swap(s[idx], s[j]); // backtrack
28 }
29 }
30 }
31
32public:
33 string findMaximumNum(string s, int k) {
34 string maxStr = s;
35 solve(s, 0, k, maxStr);
36 return maxStr;
37 }
38};
39
40int main() {
41 Solution sol;
42 cout << sol.findMaximumNum("7599", 2) << endl;
43 return 0;
44}

Time & Space Complexity

  • Time complexity: O(N^K) — Pruning non-maximum suffix digits limits branching factor to the frequency of maximum digits.
  • Space complexity: O(N) — Recursion depth is bounded by string length N.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.All-Pairs Swap BacktrackingO(N^(2K))O(K)Swap all pairs (i, j) where s[i] < s[j].O(N2) branching per level
2.Index-Guided BacktrackingO(N^K)O(N)Process left-to-right, swapping with any larger suffix digit.Suboptimal suffix branching
3.Suffix Maximum Only SwappingOptimalO(N^K)O(N)Only swap with occurrences of the absolute maximum suffix digit.Duplicate max digit branching

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Only swapping with the first occurrence of maxChar instead of exploring all occurrences of maxChar.

Pitfall 2:

Decrementing k even when no swap occurred at idx.

Pitfall 3:

Forgetting to swap back (backtrack).

Crucial Edge Cases to Validate:

  • Already Maximum: s = 9876, k = 2 -> returns 9876.
  • k Larger than Needed: s = 12, k = 5 -> returns 21.
  • All Digits Identical: s = 9999, k = 3 -> returns 9999.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the 7599 counter-example to show the interviewer why greedy choice is insufficient and backtracking is necessary.
  2. Highlight the suffix maximum pruning optimization.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does a purely greedy approach fail for inputs like s = '7599', k = 2?

2.If maxChar == s[idx], should k be decremented?

Back to DSA Sheet