Transform a numeric string by repeatedly applying constrained operations to obtain the lexicographically smallest possible result.
Given a string s consisting of digits, you may repeatedly apply an operation that changes a digit by moving a fixed distance around the digit cycle 0-9. For each position, the amount you can change is constrained by an overall budget k. Your task is to produce the lexicographically smallest string that can be formed without exceeding the allowed total operation cost.
The core challenge is to decide, for each character from left to right, how much it can be reduced while preserving feasibility for the remaining characters.
Input Format
Input
- A numeric string
s. - An integer constraint
krepresenting the maximum total allowed transformation cost.
Interpretation
- Each digit can be shifted on a circular scale of digits
0through9. - The cost of changing a digit is the minimum circular distance needed for the chosen transformation.
- The total cost across all positions must not exceed
k.
Output Format
Output
- Return the lexicographically smallest string obtainable within the constraint.
Constraints
1 <= |s| <= $10^{5}$scontains only digits0-90 <= k <= $10^{9}$
Note: Exact official constraints may differ; these are prep-oriented bounds consistent with the problem title.
Example 1
Input
s = "5525", k = 5
Output
"0020"
Explanation
Using the allowed budget, reduce the earliest digits as much as possible while keeping later positions feasible. The best achievable result is lexicographically smallest.
Example 2
Input
s = "74", k = 2
Output
"52"
Explanation
The first digit can be shifted down by 2 at minimum cost, giving the smallest valid leading character. The remaining digit stays unchanged.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.