Largest number by changing up to k digits to 5

You are given a string s that holds a positive integer (digits only, no leading zero) and an integer k.

In one operation you pick any digit of s that is not 5 and change it to 5. You may perform at most k operations.

Implement:

def maximize_with_fives(s: str, k: int) -> str: ...

Return the largest number you can obtain, as a string.

Constraints

• 1 <= len(s) <= 10^5
• 0 <= k <= 10^5
• The number may be too large for a 64-bit integer, so work with the string.

Example 1

s = "1234", k = 2
output: "5534"

Change the 1 and the 2. Changing the 3 or 4 instead gives a smaller result.

Example 2

s = "9183", k = 1
output: "9583"

The leading 9 would get smaller, so leave it. The best single change is the 1.

Part 2. Now you must use exactly k operations. Return the largest result, or report that it is impossible when s has fewer than k digits that are not 5.

Reconstructed from the reported question; details may differ from what interviewers ask.