Mayor número menor que igual a B que se puede formar a partir de los dígitos de A

Dados dos enteros A y B , la tarea es encontrar el mayor número ≤ B que se puede formar usando todos los dígitos de A .
Ejemplos: 
 

Entrada: A = 123, B = 222 
Salida: 213 
123, 132 y 213 son los únicos números válidos que son ≤ 222. 
213 es el máximo entre ellos.
Entrada: A = 3921, B = 10000 
Salida: 9321 
 

Enfoque: Construyamos la respuesta dígito por dígito comenzando desde el extremo izquierdo. Necesitamos construir una respuesta máxima lexicográficamente, por lo que debemos elegir el dígito más grande en cada paso.
Iterar sobre todos los dígitos posibles a partir del mayor. Para cada dígito, compruebe si es posible ponerlo en esta posición. Para esto, construya un sufijo mínimo (coloque con avidez el dígito más bajo) y compare el número resultante con B. Si es menor o igual que B, continúe con el siguiente dígito.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the greatest number
// not gtreater than B that can be formed
// with the digits of A
string Permute_Digits(string a, long long b)
{
    // To store size of A
    int n = a.size();
 
    // To store the required answer
    string ans = "";
 
    // Traverse from leftmost digit and
    // place a smaller digit for every
    // position.
    for (int i = 0; i < n; i++) {
 
        // Keep all digits in A
        set<char> temp(a.begin(), a.end());
 
        // To avoid leading zeros
        if (i == 0)
            temp.erase(0);
 
        // For all possible values at ith position from
        // largest value to smallest
        for (auto j = temp.rbegin(); j != temp.rend(); ++j) {
 
            // Take largest possible digit
            string s1 = ans + *j;
 
            // Keep duplicate of string a
            string s2 = a;
 
            // Remove the taken digit from s2
            s2.erase(s2.find(*j), 1);
 
            // Sort all the remaining digits of s2
            sort(s2.begin(), s2.end());
 
            // Add s2 to current s1
            s1 += s2;
 
            // If s1 is less than B then it can be
            // included in the answer. Note that
            // stoll() converts a string to lomg
            // long int.
            if (stoll(s1) <= b) {
                ans += *j;
 
                // change A to s2
                a = s2;
                break;
            }
        }
    }
 
    // Return the required answer
    return ans;
}
 
// Driver code
int main()
{
    string a = "123";
    int b = 222;
    cout << Permute_Digits(a, b);
 
    return 0;
}

# Python implementation of the approach
 
# Function to return the greatest number
# not gtreater than B that can be formed
# with the digits of A
def permuteDigits(a: str, b: int) -> str:
 
    # To store size of A
    n = len(a)
 
    # To store the required answer
    ans = ""
 
    # Traverse from leftmost digit and
    # place a smaller digit for every
    # position.
    for i in range(n):
 
        # Keep all digits in A
        temp = set(list(a))
 
        # To avoid leading zeros
        if i == 0:
            temp.discard(0)
 
        # For all possible values at ith position from
        # largest value to smallest
        for j in reversed(list(temp)):
 
            # Take largest possible digit
            s1 = ans + j
 
            # Keep duplicate of string a
            s2 = list(a).copy()
 
            # Remove the taken digit from s2
            s2.remove(j)
 
            # Sort all the remaining digits of s2
            s2 = ''.join(sorted(list(s2)))
 
            # Add s2 to current s1
            s1 += s2
 
            # If s1 is less than B then it can be
            # included in the answer. Note that
            # int() converts a string to integer
            if int(s1) <= b:
                ans += j
 
                # change A to s2
                a = ''.join(list(s2))
                break
 
    # Return the required answer
    return ans
 
# Driver Code
if __name__ == "__main__":
 
    a = "123"
    b = 222
    print(permuteDigits(a, b))
 
# This code is contributed by
# sanjeev2552

<script>
// JavaScript implementation of the approach
 
// Function to return the greatest number
// not gtreater than B that can be formed
// with the digits of A
function Permute_Digits(a,b)
{
    // To store size of A
    let n = a.length;
 
    // To store the required answer
    let ans = "";
 
    // Traverse from leftmost digit and
    // place a smaller digit for every
    // position.
    for (let i = 0; i < n; i++) {
 
        // Keep all digits in A
        let temp = new Set()
        for(let i=0;i<n;i++){
            if(a[i] !== '0')temp.add(a[i])
        }
 
        // For all possible values at ith position from
        // largest value to smallest
        let reverse = [...temp].reverse();
        for (let j = 0; j < reverse.length; j++) {
 
            // Take largest possible digit
            let s1 = ans + reverse[j];
 
            // Keep duplicate of string a
            let s2 = a;
 
            // Remove the taken digit from s2
            s2 = s2.replace(reverse[j], '');
 
            // Sort all the remaining digits of s2
            s2 = [...s2].sort((a,b)=>a-b).join("");
 
            // Add s2 to current s1
            s1 += s2;
 
            // If s1 is less than B then it can be
            // included in the answer. Note that
            // Number() converts a string to Number
 
            if (Number(s1) <= b) {
                ans += reverse[j];
 
                // change A to s2
                a = s2;
                break;
            }
        }
    }
 
    // Return the required answer
    return ans;
    
}
 
// Driver code
 
let a = "123";
let b = 222;
document.write(Permute_Digits(a, b));
 
// This code is contributed by shinjanpatra.
</script>

213

Complejidad de tiempo: O(|a| ² )

Espacio Auxiliar: O(|a|)

Optimizaciones : podemos usar multiset para mantener todas las ocurrencias de un dígito en el conjunto. También podemos hacer una búsqueda binaria usando lower_bound() en C++ para encontrar rápidamente el dígito que se colocará.