Número más grande que no exceda N que no contenga ninguno de los dígitos de S

Dada una string numérica N ( 1 ≤ |N| ≤ 10 ⁵ ) y otra string numérica S ( 1 ≤ |S| ≤ 10 ⁵ ), la tarea es encontrar el número máximo ≤ N tal que no contenga dígitos de cuerda S. _ Elimine los ceros iniciales, si es necesario. 

Nota: La string S no contiene ‘0’ .

Ejemplos:

Entrada: N = “2004”, S = “2” 
Salida: 1999 
Explicación:  
2 004 tiene el dígito 2 que está en la string S. 
Por lo tanto, siga reduciéndolo en 1 hasta que el número obtenido no contenga 2. 
Por lo tanto, el mayor número que se puede obtener es 1999.

Entrada: N = “12345”, S = “23” 
Salida: 11999

Enfoque ingenuo: para cada valor de N , verifique si contiene alguno de los dígitos de S . Continúe reduciendo N en 1 hasta que cualquier dígito que esté presente en S no aparezca en N . 

Complejidad de tiempo: O(|N| * log(|N|) * |S|) 
Espacio auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar utilizando Hashing . Siga los pasos a continuación para resolver el problema:

• Iterar sobre los caracteres de la string S y almacenar los distintos caracteres de S en un Map .
• Atraviesa la cuerda N.
• Si se encuentra que algún dígito de N está presente en S , digamos idx ^th dígito, reduzca N[idx] al dígito más grande que no está presente en S , digamos LargestDig .
• Dígitos en rango [idx + 1, |N| – 1] se cambian a LargestDig . 
   

Ilustración: 
Considere N = “2004” y S = “2”. 
Para eliminar 2 , se cambia a 1 y los dígitos restantes se cambian al dígito más grande que no está presente en S , que es el dígito 9 .

• Elimina todos los ceros iniciales del número.

A continuación se muestra la implementación del enfoque anterior.

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to obtain the largest number not exceeding
// num which does not contain any digits present in S
string greatestReducedNumber(string num, string s)
{
    // Stores digits of S
    vector<bool> vis_s(10, false);
 
    // Traverse the string S
    for (int i = 0; i < (int)s.size(); i++) {
 
        // Set occurrence as true
        vis_s[int(s[i]) - 48] = true;
    }
 
    int n = num.size();
    int in = -1;
 
    // Traverse the string n
    for (int i = 0; i < n; i++) {
        if (vis_s[(int)num[i] - '0']) {
            in = i;
            break;
        }
    }
 
    // All digits of num are not
    // present in string s
    if (in == -1) {
        return num;
    }
 
    for (char dig = num[in]; dig >= '0'; dig--) {
        if (vis_s[(int)dig - '0'] == 0) {
            num[in] = dig;
            break;
        }
    }
 
    char LargestDig = '0';
 
    for (char dig = '9'; dig >= '0'; dig--) {
        if (vis_s[dig - '0'] == false) {
 
            // Largest Digit not present
            // in the string s
            LargestDig = dig;
            break;
        }
    }
 
    // Set all digits from positions
    // in + 1 to n - 1 as LargestDig
    for (int i = in + 1; i < n; i++) {
        num[i] = LargestDig;
    }
 
    // Counting leading zeroes
    int Count = 0;
    for (int i = 0; i < n; i++) {
        if (num[i] == '0')
            Count++;
        else
            break;
    }
 
    // Removing leading zeroes
    num.erase(0, Count);
 
    // If the string becomes null
    if ((int)num.size() == 0)
        return "0";
 
    // Return the largest number
    return num;
}
 
// Driver Code
int main()
{
    string N = "12345";
    string S = "23";
 
    cout << greatestReducedNumber(N, S);
 
    return 0;
}

// Java program to implement
// the above approach
 
import java.io.*;
import java.util.Arrays;
 
class GFG {
 
    // Function to obtain the largest number not exceeding
    // num which does not contain any digits present in S
    static String greatestReducedNumber(String num,
                                        String s)
    {
        // Stores digits of S
        Boolean[] vis_s = new Boolean[10];
        Arrays.fill(vis_s, Boolean.FALSE);
 
        // Traverse the string S
        for (int i = 0; i < (int)s.length(); i++) {
 
            // Set occurrence as true
            vis_s[(int)(s.charAt(i)) - 48] = true;
        }
 
        int n = num.length();
        int in = -1;
 
        // Traverse the string n
        for (int i = 0; i < n; i++) {
            if (vis_s[(int)num.charAt(i) - '0']) {
                in = i;
                break;
            }
        }
 
        // All digits of num are not
        // present in string s
        if (in == -1) {
            return num;
        }
 
    for (char dig = num.charAt(in); dig >= '0'; dig--) {
        if (vis_s[(int)dig - '0'] == false) {
            num = num.substring(0, in) + dig
                  + num.substring(in + 1, n);
            break;
        }
    }
 
    char LargestDig = '0';
 
    for (char dig = '9'; dig >= '0'; dig--) {
        if (vis_s[dig - '0'] == false) {
 
            // Largest Digit not present
            // in the string s
            LargestDig = dig;
            break;
        }
    }
 
    // Set all digits from positions
    // in + 1 to n - 1 as LargestDig
    for (int i = in + 1; i < n; i++) {
        num = num.substring(0, i) + LargestDig;
    }
 
    // Counting leading zeroes
    int Count = 0;
    for (int i = 0; i < n; i++) {
        if (num.charAt(i) == '0')
            Count++;
        else
            break;
    }
 
    // Removing leading zeroes
    num = num.substring(Count, n);
 
    // If the string becomes null
    if ((int)num.length() == 0)
        return "0";
 
    // Return the largest number
    return num;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        String N = "12345";
        String S = "23";
 
        System.out.print(greatestReducedNumber(N, S));
    }
}
 
// This code is contributed by subhammahato348

# Python3 program to implement
# the above approach
 
# Function to obtain the largest number not exceeding
# num which does not contain any digits present in S
def greatestReducedNumber(num, s) :
  
    # Stores digits of S
    vis_s = [False] * 10
     
    # Traverse the string S
    for i in range(len(s)) :
     
      # Set occurrence as true
      vis_s[(ord)(s[i]) - 48] = True   
    n = len(num)
    In = -1
     
    # Traverse the string n
    for i in range(n) :
      if (vis_s[ord(num[i]) - ord('0')]) :
        In = i
        break
     
    # All digits of num are not
    # present in string s
    if (In == -1) :
      return num   
    for dig in range(ord(num[In]), ord('0') - 1, -1) :
      if (vis_s[dig - ord('0')] == False) :
        num = num[0 : In] + chr(dig) + num[In + 1 : n - In - 1]
        break   
    LargestDig = '0'
    for dig in range(ord('9'), ord('0') - 1, -1) :
      if (vis_s[dig - ord('0')] == False) :
     
        # Largest Digit not present
        # in the string s
        LargestDig = dig
        break
     
    # Set all digits from positions
    # in + 1 to n - 1 as LargestDig
    for i in range(In + 1, n) :
      num = num[0 : i] + chr(LargestDig)
     
    # Counting leading zeroes
    Count = 0
    for i in range(n) :
      if (num[i] == '0') :
        Count += 1
      else :
        break
     
    # Removing leading zeroes
    num = num[Count : n]
     
    # If the string becomes null
    if (int(len(num)) == 0) :
      return "0"
     
    # Return the largest number
    return num
     
    # Driver code
N = "12345"
S = "23"
 
print(greatestReducedNumber(N, S))
 
# This code is contributed by divyeshrabadiya07.

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;  
class GFG
{
 
  // Function to obtain the largest number not exceeding
  // num which does not contain any digits present in S
  static string greatestReducedNumber(string num, string s)
  {
     
    // Stores digits of S
    bool[] vis_s = new bool[10];
 
    // Traverse the string S
    for (int i = 0; i < (int)s.Length; i++) {
 
      // Set occurrence as true
      vis_s[(int)(s[i]) - 48] = true;
    }
 
    int n = num.Length;
    int In = -1;
 
    // Traverse the string n
    for (int i = 0; i < n; i++) {
      if (vis_s[(int)num[i] - '0']) {
        In = i;
        break;
      }
    }
 
    // All digits of num are not
    // present in string s
    if (In == -1) {
      return num;
    }
 
    for (char dig = num[In]; dig >= '0'; dig--) {
      if (vis_s[(int)dig - '0'] == false) {
        num = num.Substring(0, In) + dig + num.Substring(In + 1, n - In - 1);
        break;
      }
    }
 
    char LargestDig = '0';
 
    for (char dig = '9'; dig >= '0'; dig--) {
      if (vis_s[dig - '0'] == false) {
 
        // Largest Digit not present
        // in the string s
        LargestDig = dig;
        break;
      }
    }
 
    // Set all digits from positions
    // in + 1 to n - 1 as LargestDig
    for (int i = In + 1; i < n; i++) {
      num = num.Substring(0, i) + LargestDig;
    }
 
    // Counting leading zeroes
    int Count = 0;
    for (int i = 0; i < n; i++) {
      if (num[i] == '0')
        Count++;
      else
        break;
    }
 
    // Removing leading zeroes
    num = num.Substring(Count, n);
 
    // If the string becomes null
    if ((int)num.Length == 0)
      return "0";
 
    // Return the largest number
    return num;
  }
 
  // Driver code
  static void Main() {
    string N = "12345";
    string S = "23";
 
    Console.Write(greatestReducedNumber(N, S));
  }
}
 
// This code is contributed by divyesh072019

<script>
// JavaScript program to implement
// the above approach
 
// Function to obtain the largest number not exceeding
// num which does not contain any digits present in S
function greatestReducedNumber( num, s){
    // Stores digits of S
    let vis_s = [false,false,false,false,false,false,false,false,false,false];
 
    // Traverse the string S
    for (let i = 0; i < s.length; i++) {
        // Set occurrence as true
        vis_s[Number(s[i]) - 48] = true;
    }
 
    let n = num.length;
    let inn = -1;
 
    // Traverse the string n
    for (let i = 0; i < n; i++) {
        if (vis_s[Number(num[i]) - '0']) {
            inn = i;
            break;
        }
    }
 
    // All digits of num are not
    // present in string s
    if (inn == -1) {
        return num;
    }
 
    for (let dig = String(num[inn]); dig >= '0'; dig--) {
        if (vis_s[Number(dig) - '0'] == 0) {
            num[inn] = dig;
            break;
        }
    }
 
    let LargestDig = '0';
 
    for (let dig = '9'; dig >= '0'; dig--) {
        if (vis_s[dig - '0'] == false) {
 
            // Largest Digit not present
            // in the string s
            LargestDig = dig;
            break;
        }
    }
 
    // Set all digits from positions
    // in + 1 to n - 1 as LargestDig
    for (let i = inn + 1; i < n; i++) {
        num[i] = LargestDig;
    }
 
    // Counting leading zeroes
    let Count = 0;
    for (let i = 0; i < n; i++) {
        if (num[i] == '0')
            Count++;
        else
            break;
    }
 
    // Removing leading zeroes
    num = Number(num).toString();
 
    // If the string becomes null
    if (num.length == 0)
        return "0";
 
    // Return the largest number
    return num;
}
 
// Driver Code
let N = "12345";
let S = "23";
document.write( greatestReducedNumber(N, S));
 
// This code is contributed by rohitsingh07052
</script>

11999

Complejidad temporal: O(|N| + |s|) 
Espacio auxiliar: O(1)