Katkat
Back

Find smallest permutation under constraints

AirbnbSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to manipulate digits and understand greedy strategies to construct the smallest possible number after applying specific constraints.

Problem: Smallest Permutation Under Constraints

Given a positive integer n represented as a string, you are allowed to swap any two digits of the number at most k times. Your goal is to find the smallest possible integer (as a string) that can be obtained after performing at most k swaps.

Note: The result must not have a leading zero unless the number is exactly "0".

Function Signature

def find_smallest_permutation(n: str, k: int) -> str:

Constraints

  • 1 <= len(n) <= 15
  • 0 <= k <= 10
  • n contains only digits '0'-'9'.

Examples

Example 1: Input: n = "4321", k = 1 Output: "1324" Explanation: Swapping '4' and '1' yields the smallest possible result.

Example 2: Input: n = "201", k = 1 Output: "102" Explanation: Swapping '2' and '1' gives '102'. We cannot swap '2' with '0' as it would result in a leading zero.

Edge Cases

  • k = 0: The number remains unchanged.
  • Numbers that already have leading zeros are not allowed.
  • If k is very large, return the globally smallest permutation (sorted order).

Hints

Hint 1

Consider a greedy approach: for each position from left to right, try to find the smallest possible digit that can be moved there.

Hint 2

Since the length of the string is small (up to 15), you can use recursion with memoization or a depth-first search to explore potential swaps.

Hint 3

When placing a digit at the current position, ensure you skip choices that would result in a leading zero if the current index is 0 and the length of the number is greater than 1.

Follow-up questions

  • How would your approach change if the length of `n` was increased to 100 digits?
  • What is the time complexity of your solution, and can you optimize it using dynamic programming?
  • If we wanted to find the largest possible permutation instead of the smallest, how would the greedy logic change?