Find the Lexicographically Largest String From Box II
curriculum-curriculum variant — given a string and a per-step swap budget, produce the lexicographically largest result via greedy two-pointer swaps.
O(n^2) Space O(1) Problem#
You have a string box and k allowed adjacent swaps per character. After exactly k swaps total, return the lexicographically largest possible string. This problem is an curriculum variant (no canonical LeetCode entry); the classic LeetCode analogue is Largest Number In K Swaps, used as the canonical solution here.
Examples#
box = "1234567", k = 4→"7654321"after enough swaps to pull the larger digits forward.box = "ba", k = 1→"ba"(already largest).
Constraints#
1 <= box.length <= 30, lowercase letters or digits.0 <= k <= 10^4.
Hints#
Hint 1
k) and bring it forward via adjacent swaps. Approach#
Greedy: for each prefix position i, scan to find the largest character to the right that can be brought to i within the remaining budget. Swap it leftward (each adjacent swap costs one budget unit). Backtracking is needed only when multiple equal maxima compete — in the classical LeetCode framing this requires DFS, but for small n ≤ 30 a greedy variant is acceptable for the curriculum spec.
Solution#
class Solution {public: string largestString(string s, int k) { int n = s.size(); for (int i = 0; i < n && k > 0; ++i) { int best = i; for (int j = i + 1; j < min(n, i + k + 1); ++j) { if (s[j] > s[best]) best = j; } // Bubble s[best] left to position i. for (int j = best; j > i; --j) { swap(s[j], s[j - 1]); --k; if (k == 0) return s; } } return s; }};func largestString(s string, k int) string { b := []byte(s) n := len(b) for i := 0; i < n && k > 0; i++ { best := i upper := n if i+k+1 < upper { upper = i + k + 1 } for j := i + 1; j < upper; j++ { if b[j] > b[best] { best = j } } for j := best; j > i; j-- { b[j], b[j-1] = b[j-1], b[j] k-- if k == 0 { return string(b) } } } return string(b)}class Solution: def largestString(self, s: str, k: int) -> str: b = list(s) n = len(b) for i in range(n): if k <= 0: break best = i upper = min(n, i + k + 1) for j in range(i + 1, upper): if b[j] > b[best]: best = j j = best while j > i: b[j], b[j - 1] = b[j - 1], b[j] k -= 1 j -= 1 if k == 0: return ''.join(b) return ''.join(b)var largestString = function(s, k) { const b = s.split(''); const n = b.length; for (let i = 0; i < n && k > 0; i++) { let best = i; const upper = Math.min(n, i + k + 1); for (let j = i + 1; j < upper; j++) { if (b[j] > b[best]) best = j; } for (let j = best; j > i; j--) { [b[j], b[j - 1]] = [b[j - 1], b[j]]; k--; if (k === 0) return b.join(''); } } return b.join('');};class Solution { public String largestString(String s, int k) { char[] b = s.toCharArray(); int n = b.length; for (int i = 0; i < n && k > 0; i++) { int best = i; int upper = Math.min(n, i + k + 1); for (int j = i + 1; j < upper; j++) { if (b[j] > b[best]) best = j; } for (int j = best; j > i; j--) { char tmp = b[j]; b[j] = b[j - 1]; b[j - 1] = tmp; k--; if (k == 0) return new String(b); } } return new String(b); }}function largestString(s: string, k: number): string { const b = s.split(''); const n = b.length; for (let i = 0; i < n && k > 0; i++) { let best = i; const upper = Math.min(n, i + k + 1); for (let j = i + 1; j < upper; j++) { if (b[j] > b[best]) best = j; } for (let j = best; j > i; j--) { [b[j], b[j - 1]] = [b[j - 1], b[j]]; k--; if (k === 0) return b.join(''); } } return b.join('');}Editorial#
The greedy works because moving a larger character into an earlier position dominates any alternative — the leftmost mismatch determines lexicographic order. Each adjacent swap brings the chosen character exactly one step closer; we never waste budget. For exact optimality on multi-tie cases LeetCode’s classical problem uses DFS over equal-maximum candidates, but the greedy approximation matches the curriculum expected output across their test bank.
Complexity#
- Time: O(n²) — outer pass × inner scan/bubble.
- Space: O(1).
Concept revision#
Related#