Katkat
Back

Rearrange Digits Without Adjacent Sums Above Nine

AmazonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Rearrange a multiset of digits into the lexicographically smallest string such that every adjacent pair sums to at most nine, or return an empty string if impossible.

Problem Statement

Given a string s consisting of decimal digits ('0' through '9'), rearrange all the digits such that the sum of every two adjacent digits is at most 9. That is, for every index i from 0 to len(s) - 2, the condition int(result[i]) + int(result[i + 1]) <= 9 must hold.

Return the lexicographically smallest valid arrangement as a string. If no such arrangement exists, return an empty string "".

Leading zeroes are valid and should be preserved (e.g., "012" is a valid result if it satisfies the condition).

Function Interface

def rearrange_digits(s: str) -> str:
    pass

Examples

Example 1

Input: s = "9801"
Output: "1809"
Explanation:
- '1' + '8' = 9  9.
"1809" is the lexicographically smallest valid string using all digits.

Example 2

Input: s = "567"
Output: ""
Explanation:
All digits are >= 5. Any adjacent pair would sum to at least 5 + 6 = 11 > 9, so no valid rearrangement is possible.

Example 3

Input: s = "000"
Output: "000"
Explanation:
Every pair sums to 0 <= 9, and "000" is already minimal.

Constraints

  • 1 <= len(s) <= 100
  • s consists only of decimal digits '0' through '9'.

Hints

Hint 1

Observe that any two digits greater than or equal to 5 cannot be placed next to each other because their sum is at least 10.

Hint 2

Since the answer must be lexicographically smallest, consider constructing the string greedily from left to right by picking the smallest available valid digit at each position.

Hint 3

After placing a digit, ensure a valid sequence can still be formed with the remaining counts; use backtracking with memoization over the state (remaining counts tuple, previous digit).

Follow-up questions

  • How does the difficulty of the problem change if the threshold sum is an arbitrary integer K instead of 9?
  • Can the feasibility check for the remaining digits be modeled as a bipartite matching or flow problem to support input lengths up to 10^5?
  • What is the maximum number of digits greater than or equal to 5 that a string of length N can contain for a valid arrangement to be possible?