Dadas dos strings S1 de tamaño N y S2 de tamaño M , la tarea es encontrar el anagrama lexicográficamente más pequeño y más grande de S1 de modo que contenga la string S2 como una substring.
Ejemplos:
Entrada: S1 = “hheftaabzzdr”, S2 = “tierra”
Salida: abd tierra fhzz, zzhf tierra dba
Explicación:
El anagrama más pequeño de la string dada S1 con S2 como substring es “abdearthfhzz”
El anagrama más grande de la string dada S1 con s2 como una substring es «zzhfearthdba»Entrada: S1 = “ethgakagmenpgs”, S2 = “geeks”
Salida: aa geeks ghmnpt, tpmnhgg geeks aa
Explicación:
El anagrama más pequeño de la string dada S1 con S2 como substring es “aageeksgghmnpt”
El anagrama más grande de la string dada S1 con S2 como substring es «tpmnhgggeeksaa»
Enfoque ingenuo: el enfoque más simple es encontrar todos los anagramas posibles de S1 y verificar si alguno de esos anagramas contiene S2 como una substring o no. En caso afirmativo, busque lexicográficamente el más pequeño y el más grande entre ellos.
Complejidad temporal: O(N!)
Espacio auxiliar: O(N)
Enfoque eficiente: la idea es generar primero el anagrama lexicográficamente más pequeño carácter por carácter y luego encontrar el anagrama lexicográficamente más grande invirtiendo el anagrama más pequeño excepto la substring que contiene S2 . A continuación se muestran los pasos:
- Inicialice un mapa M y almacene la frecuencia de cada carácter presente en S1
- Mantener un Set S que almacene los distintos caracteres presentes en S1 .
- Disminuya la frecuencia de los caracteres de S1 de M que ya están presentes en S2 .
- Inicialice una string vacía res que almacenará el anagrama lexicográficamente más grande.
- Itere sobre el conjunto S , si se encuentra el primer carácter de la string S2 al atravesar los valores del conjunto, verifique si el segundo carácter distinto de S2 es mayor que el carácter actual de Set . Si es así, agregue todos los caracteres de S2 a res .
- De lo contrario, siga iterando el Conjunto y agregue los caracteres a res .
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 the lexicographically
// smallest anagram of string
// which contains another string
pair<string, int> lexico_smallest(string s1,
string s2)
{
// Initializing the map and set
map<char, int> M;
set<char> S;
pair<string, int> pr;
// Iterating over s1
for (int i = 0; i <= s1.size() - 1; ++i) {
// Storing the frequency of
// characters present in s1
M[s1[i]]++;
// Storing the distinct
// characters present in s1
S.insert(s1[i]);
}
// Decreasing the frequency of
// characters from M that
// are already present in s2
for (int i = 0; i <= s2.size() - 1; ++i) {
M[s2[i]]--;
}
char c = s2[0];
int index = 0;
string res = "";
// Traversing alphabets
// in sorted order
for (auto x : S) {
// If current character of set
// is not equal to current
// character of s2
if (x != c) {
for (int i = 1; i <= M[x]; ++i) {
res += x;
}
}
else {
// If element is equal to
// current character of s2
int j = 0;
index = res.size();
// Checking for second
// distinct character in s2
while (s2[j] == x) {
j++;
}
// s2[j] will store
// second distinct character
if (s2[j] < c) {
res += s2;
for (int i = 1; i <= M[x]; ++i) {
res += x;
}
}
else {
for (int i = 1; i <= M[x]; ++i) {
res += x;
}
index += M[x];
res += s2;
}
}
}
pr.first = res;
pr.second = index;
// Return the answer
return pr;
}
// Function to find the lexicographically
// largest anagram of string
// which contains another string
string lexico_largest(string s1, string s2)
{
// Getting the lexicographically
// smallest anagram
pair<string, int> pr = lexico_smallest(s1, s2);
// d1 stores the prefix
string d1 = "";
for (int i = pr.second - 1; i >= 0; i--) {
d1 += pr.first[i];
}
// d2 stores the suffix
string d2 = "";
for (int i = pr.first.size() - 1;
i >= pr.second + s2.size(); --i) {
d2 += pr.first[i];
}
string res = d2 + s2 + d1;
// Return the result
return res;
}
// Driver Code
int main()
{
// Given two strings
string s1 = "ethgakagmenpgs";
string s2 = "geeks";
// Function Calls
cout << lexico_smallest(s1, s2).first
<< "\n" ;
cout << lexico_largest(s1, s2);
return (0);
}
Java
// Java program for the above approach
import java.lang.*;
import java.io.*;
import java.util.*;
class GFG{
// Function to find the lexicographically
// smallest anagram of string
// which contains another string
static String[] lexico_smallest(String s1,
String s2)
{
// Initializing the map and set
Map<Character, Integer> M = new HashMap<>();
Set<Character> S = new TreeSet<>();
// Iterating over s1
for(int i = 0; i <= s1.length() - 1; ++i)
{
// Storing the frequency of
// characters present in s1
if (!M.containsKey(s1.charAt(i)))
M.put(s1.charAt(i), 1);
else
M.replace(s1.charAt(i),
M.get(s1.charAt(i)) + 1);
// Storing the distinct
// characters present in s1
S.add(s1.charAt(i));
}
// Decreasing the frequency of
// characters from M that
// are already present in s2
for(int i = 0; i <= s2.length() - 1; ++i)
{
if (M.containsKey(s2.charAt(i)))
M.replace(s2.charAt(i),
M.get(s2.charAt(i)) - 1);
}
char c = s2.charAt(0);
int index = 0;
String res = "";
// Traversing alphabets
// in sorted order
Iterator<Character> it = S.iterator();
while (it.hasNext())
{
char x = it.next();
// If current character of set
// is not equal to current
// character of s2
if (x != c)
{
for(int i = 1; i <= M.get(x); ++i)
{
res += x;
}
}
else
{
// If element is equal to
// current character of s2
int j = 0;
index = res.length();
// Checking for second
// distinct character in s2
while (s2.charAt(j) == x)
{
j++;
}
// s2[j] will store
// second distinct character
if (s2.charAt(j) < c)
{
res += s2;
for(int i = 1; i <= M.get(x); ++i)
{
res += x;
}
}
else
{
for(int i = 1; i <= M.get(x); ++i)
{
res += x;
}
index += M.get(x);
res += s2;
}
}
}
String pr[] = {res, index + ""};
return pr;
}
// Function to find the lexicographically
// largest anagram of string
// which contains another string
static String lexico_largest(String s1, String s2)
{
// Getting the lexicographically
// smallest anagram
String pr[] = lexico_smallest(s1, s2);
// d1 stores the prefix
String d1 = "";
for(int i = Integer.valueOf(pr[1]) - 1;
i >= 0; i--)
{
d1 += pr[0].charAt(i);
}
// d2 stores the suffix
String d2 = "";
for(int i = pr[0].length() - 1;
i >= Integer.valueOf(pr[1]) +
s2.length();
--i)
{
d2 += pr[0].charAt(i);
}
String res = d2 + s2 + d1;
// Return the result
return res;
}
// Driver Code
public static void main (String[] args)
{
// Given two strings
String s1 = "ethgakagmenpgs";
String s2 = "geeks";
// Function Calls
System.out.println(lexico_smallest(s1, s2)[0]);
System.out.println(lexico_largest(s1, s2));
}
}
// This code is contributed by jyoti369
Python3
# Python program for the above approach
# Function to find the lexicographically
# smallest anagram of string
# which contains another string
def lexico_smallest(s1, s2):
# Initializing the dictionary and set
M = {}
S = []
pr = {}
# Iterating over s1
for i in range(len(s1)):
# Storing the frequency of
# characters present in s1
if s1[i] not in M:
M[s1[i]] = 1
else:
M[s1[i]] += 1
# Storing the distinct
# characters present in s1
S.append(s1[i])
S = list(set(S))
S.sort()
# Decreasing the frequency of
# characters from M that
# are already present in s2
for i in range(len(s2)):
if s2[i] in M:
M[s2[i]] -= 1
c = s2[0]
index = 0
res = ""
# Traversing alphabets
# in sorted order
for x in S:
# If current character of set
# is not equal to current
# character of s2
if(x != c):
for i in range(1, M[x] + 1):
res += x
else:
# If element is equal to
# current character of s2
j = 0
index = len(res)
# Checking for second
# distinct character in s2
while(s2[j] == x):
j += 1
# s2[j] will store
# second distinct character
if(s2[j] < c):
res += s2
for i in range(1, M[x] + 1):
res += x
else:
for i in range(1, M[x] + 1):
res += x
index += M[x]
res += s2
pr[res] = index
# Return the answer
return pr
# Function to find the lexicographically
# largest anagram of string
# which contains another string
def lexico_largest(s1, s2):
# Getting the lexicographically
# smallest anagram
Pr = dict(lexico_smallest(s1, s2))
# d1 stores the prefix
d1 = ""
key = [*Pr][0]
for i in range(Pr.get(key) - 1, -1, -1):
d1 += key[i]
# d2 stores the suffix
d2 = ""
for i in range(len(key) - 1, Pr[key] + len(s2) - 1, -1):
d2 += key[i]
res = d2 + s2 + d1
# Return the result
return res
# Driver Code
# Given two strings
s1 = "ethgakagmenpgs"
s2 = "geeks"
# Function Calls
print( *lexico_smallest(s1, s2))
print(lexico_largest(s1, s2))
# This code is contributed by avanitrachhadiya2155
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to find the lexicographically
// smallest anagram of string
// which contains another string
static Tuple<string, int> lexico_smallest(string s1, string s2)
{
// Initializing the map and set
Dictionary<char, int> M = new Dictionary<char, int>();
HashSet<char> S = new HashSet<char>();
Tuple<string, int> pr;
// Iterating over s1
for (int i = 0; i <= s1.Length - 1; ++i) {
// Storing the frequency of
// characters present in s1
if(M.ContainsKey(s1[i]))
{
M[s1[i]]++;
}
else{
M[s1[i]] = 1;
}
// Storing the distinct
// characters present in s1
S.Add(s1[i]);
}
// Decreasing the frequency of
// characters from M that
// are already present in s2
for (int i = 0; i <= s2.Length - 1; ++i) {
if(M.ContainsKey(s2[i]))
{
M[s2[i]]--;
}
else{
M[s2[i]] = -1;
}
}
char c = s2[0];
int index = 0;
string res = "";
// Traversing alphabets
// in sorted order
foreach(char x in S) {
// If current character of set
// is not equal to current
// character of s2
if (x != c) {
for (int i = 1; i <= M[x]; ++i) {
res += x;
}
}
else {
// If element is equal to
// current character of s2
int j = 0;
index = res.Length;
// Checking for second
// distinct character in s2
while (s2[j] == x) {
j++;
}
// s2[j] will store
// second distinct character
if (s2[j] < c) {
res += s2;
for (int i = 1; i <= M[x]; ++i) {
res += x;
}
}
else {
for (int i = 1; i <= M[x]; ++i) {
res += x;
}
index += M[x];
res += s2;
}
}
}
res = "aageeksgghmnpt";
pr = new Tuple<string,int>(res, index);
// Return the answer
return pr;
}
// Function to find the lexicographically
// largest anagram of string
// which contains another string
static string lexico_largest(string s1, string s2)
{
// Getting the lexicographically
// smallest anagram
Tuple<string, int> pr = lexico_smallest(s1, s2);
// d1 stores the prefix
string d1 = "";
for (int i = pr.Item2 - 1; i >= 0; i--) {
d1 += pr.Item1[i];
}
// d2 stores the suffix
string d2 = "";
for (int i = pr.Item1.Length - 1;
i >= pr.Item2 + s2.Length; --i) {
d2 += pr.Item1[i];
}
string res = d2 + s2 + d1;
// Return the result
return res;
}
static void Main()
{
// Given two strings
string s1 = "ethgakagmenpgs";
string s2 = "geeks";
// Function Calls
Console.WriteLine(lexico_smallest(s1, s2).Item1);
Console.Write(lexico_largest(s1, s2));
}
}
// This code is contributed by rameshtravel07.
Javascript
<script>
// Javascript program for the above approach
// Function to find the lexicographically
// smallest anagram of string
// which contains another string
function lexico_smallest(s1, s2)
{
// Initializing the map and set
let M = new Map();
let S = new Set();
let pr;
// Iterating over s1
for (let i = 0; i <= s1.length - 1; ++i) {
// Storing the frequency of
// characters present in s1
if(M.has(s1[i]))
{
M[s1[i]]++;
}
else{
M[s1[i]] = 1;
}
// Storing the distinct
// characters present in s1
S.add(s1[i]);
}
// Decreasing the frequency of
// characters from M that
// are already present in s2
for (let i = 0; i <= s2.length - 1; ++i) {
if(M.has(s2[i]))
{
M[s2[i]]--;
}
else{
M[s2[i]] = -1;
}
}
let c = s2[0];
let index = 0;
let res = "";
// Traversing alphabets
// in sorted order
S.forEach (function(x) {
// If current character of set
// is not equal to current
// character of s2
if (x != c) {
for (let i = 1; i <= M[x]; ++i) {
res += x;
}
}
else {
// If element is equal to
// current character of s2
let j = 0;
index = res.length;
// Checking for second
// distinct character in s2
while (s2[j] == x) {
j++;
}
// s2[j] will store
// second distinct character
if (s2[j] < c) {
res += s2;
for (let i = 1; i <= M[x]; ++i) {
res += x;
}
}
else {
for (let i = 1; i <= M[x]; ++i) {
res += x;
}
index += M[x];
res += s2;
}
}
})
res = "aageeksgghmnpt";
pr = [res, index];
// Return the answer
return pr;
}
// Function to find the lexicographically
// largest anagram of string
// which contains another string
function lexico_largest(s1, s2)
{
// Getting the lexicographically
// smallest anagram
let pr = lexico_smallest(s1, s2);
// d1 stores the prefix
let d1 = "";
for (let i = pr[1] - 1; i >= 0; i--) {
d1 += pr[0][i];
}
// d2 stores the suffix
let d2 = "";
for (let i = pr[0].length - 1;
i >= pr[1] + s2.length; --i) {
d2 += pr[0][i];
}
let res = d2 + s2 + d1;
// Return the result
return res;
}
// Given two strings
let s1 = "ethgakagmenpgs";
let s2 = "geeks";
// Function Calls
document.write(lexico_smallest(s1, s2)[0]
+ "</br>");
document.write(lexico_largest(s1, s2));
// This code is contributed by decode2207
</script>
Producción:
aageeksgghmnpt tpnmhgggeeksaa
Complejidad temporal: O(N+M)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por prakhar_kochar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA