Problem statement

https://binarysearch.com/problems/Next-Permutation-From-Pool/

Solution

Let us answer question: how many first elements of answer equal to elements of L. We want to take the most number of elements. Let us start to traverse from the end fo L and keep:

  1. pref is counter for prefix of L.
  2. cnt is counter for all our digit.

Then imagine that we try to build answer, where symbols [0:i+1] are equal to symbols of L. Then how to understand if we can build such an anwer?

  1. First we need to have enough frequencies in our pref_L, that is cnt[j] >= pref_L[j] for all digits 0, ..., 9.
  2. Maximum among avaliable not used yet symbols from digits should be more than L[i+1].

Complexity

It is O((m+n)*10)) for time and O(10) for space.

Code

class Solution:
    def solve(self, digits, L):
        cnt = Counter([int(i) for i in digits])
        n, m = len(digits), len(L)
        if m < n: L = "0"*(n - m) + L
        L = [int(i) for i in L]
        pref = Counter(L)
        for i in range(n - 1, -2, -1):
            cnt_d = {j: cnt[j] - pref[j] for j in range(10)}
            if min(cnt_d.values()) >= 0:
                A_max = max([j for j in range(10) if cnt_d[j]] + [-1])
                B_min = -1 if i == n-1 else L[i+1]

                if A_max > B_min:
                    for j in range(L[i + 1] + 1, 10):
                        if cnt_d[j]:
                            ans =  L[:i + 1] + [j]
                            cnt_d[j] -= 1
                            for i in range(10): ans += [i] * cnt_d[i]
                            return "".join(str(x) for x in ans).lstrip("0")
            
            pref[L[i]] -= 1