Dadas dos strings numéricas N y K (K ≤ N), donde los dígitos de K están en orden no decreciente, la tarea es reorganizar los dígitos de N de modo que K no aparezca como una subsecuencia en N . Si no es posible obtener tal permutación, imprima “-1” . De lo contrario, imprima cualquier permutación válida de N.
Ejemplos:
Entrada: N = 93039373637, K = 339
Salida: 97093736333Entrada: N=965, K=55
Salida: 965
Enfoque ingenuo: el enfoque más simple es generar cada permutación de N y verificar para cada permutación, si K aparece como una subsecuencia en ella o no. Si se encuentra que es falso para cualquier permutación, imprima esa permutación.
Complejidad temporal: O(N*N!)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar en función de la observación de que los dígitos de K están en orden no decreciente. Por lo tanto, reordene los dígitos de N en orden decreciente ordenando . Siga los pasos a continuación para resolver el problema:
- Almacene la frecuencia de los dígitos de N y K en HashMaps M1 y M2 , respectivamente.
- Iterar sobre el rango [0, 9] usando una variable, digamos i , para verificar si K tiene algún dígito con más ocurrencias que en N . Si M2[i] > M1[i] , imprima N y regrese.
- Nuevamente, itere sobre el rango [0, 9] usando una variable i para verificar si K contiene solo 1 dígito distinto. Si M2[i] es lo mismo que length(K) , entonces imprima “-1” y regrese.
- Para todos los demás casos, ordene N en orden decreciente y luego imprima N .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find a permutation of
// number N such that the number K does
// not appear as a subsequence in N
void findArrangement(string n, string k)
{
// Stores frequency of digits of N
unordered_map<char, int> um1;
for (int i = 0; i < n.size(); i++) {
um1[n[i]]++;
}
// Stores frequency of digits of K
unordered_map<char, int> um2;
for (int i = 0; i < k.size(); i++) {
um2[k[i]]++;
}
// Check if any digit in K has
// more occurrences than in N
for (int i = 0; i <= 9; i++) {
char ch = '0' + i;
// If true, print N and return
if (um2[ch] > um1[ch]) {
cout << n;
return;
}
}
// Check if K contains only a
// single distinct digit
for (int i = 0; i <= 9; i++) {
char ch = '0' + i;
// If true, print -1 and return
if (um2[ch] == k.size()) {
cout << -1;
return;
}
}
// For all other cases, sort N
// in decreasing order
sort(n.begin(), n.end(),
greater<char>());
// Print the value of N
cout << n;
}
// Driver Code
int main()
{
string N = "93039373637", K = "339";
// Function Call
findArrangement(N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find a permutation of
// number N such that the number K does
// not appear as a subsequence in N
static void findArrangement(String n, String k)
{
// Stores frequency of digits of N
HashMap<Character,Integer> um1 = new HashMap<Character,Integer>();
for (int i = 0; i < n.length(); i++)
{
if(um1.containsKey(n.charAt(i)))
{
um1.put(n.charAt(i), um1.get(n.charAt(i))+1);
}
else
{
um1.put(n.charAt(i), 1);
}
}
// Stores frequency of digits of K
HashMap<Character,Integer> um2 = new HashMap<Character,Integer>();
for (int i = 0; i < k.length(); i++) {
if(um2.containsKey(k.charAt(i))){
um2.put(k.charAt(i), um2.get(k.charAt(i))+1);
}
else{
um2.put(k.charAt(i), 1);
}
}
// Check if any digit in K has
// more occurrences than in N
for (int i = 0; i <= 9; i++)
{
char ch = (char) ('0' + i);
// If true, print N and return
if (um2.containsKey(ch) && um1.containsKey(ch)
&& um2.get(ch) > um1.get(ch))
{
System.out.print(n);
return;
}
}
// Check if K contains only a
// single distinct digit
for (int i = 0; i <= 9; i++)
{
char ch = (char) ('0' + i);
// If true, print -1 and return
if (um2.containsKey(ch) && um2.get(ch) == k.length())
{
System.out.print(-1);
return;
}
}
// For all other cases, sort N
// in decreasing order
n = sortString(n);
// Print the value of N
System.out.print(n);
}
static String sortString(String inputString)
{
// convert input string to char array
char tempArray[] = inputString.toCharArray();
// sort tempArray
Arrays.sort(tempArray);
// return new sorted string
return new String(new StringBuffer(new String(tempArray)).reverse());
}
// Driver Code
public static void main(String[] args)
{
String N = "93039373637", K = "339";
// Function Call
findArrangement(N, K);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach
# Function to find a permutation of
# number N such that the number K does
# not appear as a subsequence in N
def findArrangement(n, k) :
# Stores frequency of digits of N
um1 = dict.fromkeys(n, 0);
for i in range(len(n)):
um1[n[i]] += 1;
# Stores frequency of digits of K
um2 = dict.fromkeys(k, 0);
for i in range(len(k)) :
um2[k[i]] += 1;
# Check if any digit in K has
# more occurrences than in N
for i in range(10) :
ch = chr(ord('0') + i);
if ch in um2 :
# If true, print N and return
if (um2[ch] > um1[ch]) :
print(n, end = "");
return;
# Check if K contains only a
# single distinct digit
for i in range(10) :
ch = chr(ord('0') + i);
if ch in um2 :
# If true, print -1 and return
if (um2[ch] == len(k)) :
print(-1, end = "");
return;
# For all other cases, sort N
# in decreasing order
n = list(n)
n.sort(reverse = True)
# Print the value of N
print("".join(n));
# Driver Code
if __name__ == "__main__" :
N = "93039373637"; K = "339";
# Function Call
findArrangement(N, K);
# This code is contributed by AnkThon
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find a permutation of
// number N such that the number K does
// not appear as a subsequence in N
static void findArrangement(string n, string k)
{
// Stores frequency of digits of N
Dictionary<char, int> um1 = new Dictionary<char, int>();
for (int i = 0; i < n.Length; i++)
{
if(um1.ContainsKey(n[i]))
{
um1[n[i]]++;
}
else
{
um1[n[i]] = 1;
}
}
// Stores frequency of digits of K
Dictionary<char, int> um2 = new Dictionary<char, int>();
for (int i = 0; i < k.Length; i++)
{
if(um2.ContainsKey(k[i]))
{
um2[k[i]]++;
}
else
{
um2[k[i]] = 1;
}
}
// Check if any digit in K has
// more occurrences than in N
for (int i = 0; i <= 9; i++)
{
char ch = (char) ('0' + i);
// If true, print N and return
if (um2.ContainsKey(ch) && um1.ContainsKey(ch)
&& um2[ch] > um1[ch])
{
Console.Write(n);
return;
}
}
// Check if K contains only a
// single distinct digit
for (int i = 0; i <= 9; i++)
{
char ch = (char) ('0' + i);
// If true, print -1 and return
if (um2.ContainsKey(ch) && um2[ch] == k.Length)
{
Console.Write(-1);
return;
}
}
// For all other cases, sort N
// in decreasing order
n = sortString(n);
// Print the value of N
Console.Write(n);
}
static string sortString(string inputString)
{
// convert input string to char array
char[] tempArray = inputString.ToCharArray();
// sort tempArray
Array.Sort(tempArray);
Array.Reverse(tempArray);
// return new sorted string
return new string(tempArray);
}
// Driver codew
static void Main()
{
string N = "93039373637", K = "339";
// Function Call
findArrangement(N, K);
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// Javascript program for the above approach
// Function to find a permutation of
// number N such that the number K does
// not appear as a subsequence in N
function findArrangement(n, k)
{
// Stores frequency of digits of N
var um1 = new Map();
for (var i = 0; i < n.length; i++)
{
if(um1.has(n[i]))
{
um1.set(n[i], um1.get(n[i])+1);
}
else
{
um1.set(n[i], 1);
}
}
// Stores frequency of digits of K
var um2 = new Map();
for (var i = 0; i < k.length; i++)
{
if(um2.has(k[i]))
{
um2.set(k[i], um2.get(k[i])+1);
}
else
{
um2.set(k[i], 1);
}
}
// Check if any digit in K has
// more occurrences than in N
for (var i = 0; i <= 9; i++)
{
var ch = String.fromCharCode('0'.charCodeAt(0) + i);
// If true, print N and return
if (um2.has(ch) && um1.has(ch)
&& um2.get(ch) > um1.get(ch))
{
Console.Write(n);
return;
}
}
// Check if K contains only a
// single distinct digit
for (var i = 0; i <= 9; i++)
{
var ch = String.fromCharCode('0'.charCodeAt(0) + i);
// If true, print -1 and return
if (um2.has(ch) && um2.get(ch) == k.length)
{
document.write(-1);
return;
}
}
// For all other cases, sort N
// in decreasing order
n = sortString(n);
// Print the value of N
document.write(n);
}
function sortString(inputString)
{
// convert input string to char array
var tempArray = inputString.split('');
// sort tempArray
tempArray.sort();
tempArray.reverse();
// return new sorted string
return tempArray.join('');
}
// Driver codew
var N = "93039373637", K = "339";
// Function Call
findArrangement(N, K);
// This code is contributed by itsok.
</script>
Producción:
99776333330
Complejidad de tiempo: O(L*log (L)), donde L es el tamaño de la string N
Espacio auxiliar: O(L)
Publicación traducida automáticamente
Artículo escrito por aditya7409 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA