Dadas dos strings S1 y S2 de tamaño N y M respectivamente, la tarea es reorganizar los caracteres en la string S1 de modo que S2 no sea una subsecuencia de ella. Si no es posible hacer tales reordenamientos, imprima «-1» . De lo contrario, imprima la string reorganizada S1 .
Ejemplos:
Entrada: S1 = “abcd”, S2 = “ab”
Salida: “dcba”
Explicación:
Reorganice la string S1 como “dcba”.
Ahora, la string S2 = “ab” no es una subsecuencia de S1.Entrada: S1 = “aa”, S2 = “a”
Salida: -1
Enfoque: siga los pasos a continuación para resolver el problema:
- Almacene la frecuencia de los caracteres en la string S2 en una array auxiliar , digamos cnt[26] .
- Inicialice una variable, digamos ch , para almacenar los caracteres únicos presentes en la string S2 .
- Recorra la array cnt[] usando la variable i . Si el valor de cnt[i] es igual a M , esto significa que S2 consta de solo 1 carácter único . Guarde este carácter en ch y salga del bucle .
- Si el valor de ch no está definido, haga lo siguiente:
- Recorra la string S2 usando la variable i , si en cualquier índice S2[i] > S2[i + 1] ordene S1 en orden creciente y salga del ciclo .
- Si no se encuentra la condición anterior durante el desplazamiento, ordene S1 en orden decreciente .
- Imprime la string S1 .
- De lo contrario, almacene la ocurrencia de ch en la string S1 en freq . Si el valor de freq es menor que M , imprima S1 . De lo contrario, imprima -1 .
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 rearrange characters
// in string S1 such that S2 is not
// a subsequence of it
void rearrangeString(string s1, string s2)
{
// Store the frequencies of
// characters of string s2
int cnt[26] = { 0 };
// Traverse the string s2
for (int i = 0; i < s2.size(); i++)
// Update the frequency
cnt[s2[i] - 'a']++;
// Find the number of unique
// characters in s2
int unique = 0;
for (int i = 0; i < 26; i++)
// Increment unique by 1 if the
// condition satisfies
if (cnt[i] != 0)
unique++;
// Check if the number of unique
// characters in string s2 is 1
if (unique == 1) {
// Store the unique character
// frequency
int count_in_s2 = s2.size();
// Store occurrrence of it in s1
int count_in_s1 = 0;
// Find count of that character
// in the string s1
for (int i = 0; i < s1.size(); i++)
// Increment count by 1 if
// that unique character is
// same as current character
if (s1[i] == s2[0])
count_in_s1++;
// If count count_in_s1 is
// less than count_in_s2, then
// print s1 and return
if (count_in_s1 < count_in_s2) {
cout << s1;
return;
}
// Otherwise, there is no
// possible arrangement
cout << -1;
}
else {
// Checks if any character in
// s2 is less than its next
// character
int inc = 1;
// Iterate the string, s2
for (int i = 0; i < s2.size() - 1; i++)
// If s[i] is greater
// than the s[i+1]
if (s2[i] > s2[i + 1])
// Set inc to 0
inc = 0;
// If inc=1, print s1 in
// decreasing order
if (inc == 1) {
sort(s1.begin(),
s1.end(),
greater<char>());
cout << s1;
}
// Otherwise, print s1 in
// increasing order
else {
sort(s1.begin(), s1.end());
cout << s1;
}
}
}
// Driver code
int main()
{
string s1 = "abcd", s2 = "ab";
rearrangeString(s1, s2);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to rearrange characters
// in string S1 such that S2 is not
// a subsequence of it
static void rearrangeString(char[] s1, char[] s2)
{
// Store the frequencies of
// characters of string s2
int[] cnt = new int[26];
// Traverse the string s2
for(int i = 0; i < s2.length; i++)
// Update the frequency
cnt[s2[i] - 'a']++;
// Find the number of unique
// characters in s2
int unique = 0;
for(int i = 0; i < 26; i++)
// Increment unique by 1 if the
// condition satisfies
if (cnt[i] != 0)
unique++;
// Check if the number of unique
// characters in string s2 is 1
if (unique == 1)
{
// Store the unique character
// frequency
int count_in_s2 = s2.length;
// Store occurrence of it in s1
int count_in_s1 = 0;
// Find count of that character
// in the string s1
for(int i = 0; i < s1.length; i++)
// Increment count by 1 if
// that unique character is
// same as current character
if (s1[i] == s2[0])
count_in_s1++;
// If count count_in_s1 is
// less than count_in_s2, then
// print s1 and return
if (count_in_s1 < count_in_s2)
{
System.out.print(new String(s1));
return;
}
// Otherwise, there is no
// possible arrangement
System.out.print(-1);
}
else
{
// Checks if any character in
// s2 is less than its next
// character
int inc = 1;
// Iterate the string, s2
for(int i = 0; i < s2.length - 1; i++)
// If s[i] is greater
// than the s[i+1]
if (s2[i] > s2[i + 1])
// Set inc to 0
inc = 0;
// If inc=1, print s1 in
// decreasing order
if (inc == 1)
{
Arrays.sort(s1);
for(int k = 0; k < s1.length / 2; k++)
{
char temp = s1[k];
s1[k] = s1[s1.length - k - 1];
s1[s1.length - k - 1] = temp;
}
System.out.print(new String(s1));
}
// Otherwise, print s1 in
// increasing order
else
{
Arrays.sort(s1);
System.out.print(new String(s1));
}
}
}
// Driver code
public static void main(String[] args)
{
char[] s1 = "abcd".toCharArray();
char[] s2 = "ab".toCharArray();
rearrangeString(s1, s2);
}
}
// This code is contributed by divyesh072019
Python3
# Python3 program for the above approach
# Function to rearrange characters
# in S1 such that S2 is not
# a subsequence of it
def rearrangeString(s1, s2):
# Store the frequencies of
# characters of s2
cnt = [0]*26
# Traverse the s2
for i in range(len(s2)):
# Update the frequency
cnt[ord(s2[i]) - ord('a')] += 1
# Find the number of unique
# characters in s2
unique = 0
for i in range(26):
# Increment unique by 1 if the
# condition satisfies
if (cnt[i] != 0):
unique += 1
# Check if the number of unique
# characters in s2 is 1
if (unique == 1):
# Store the unique character
# frequency
count_in_s2 = len(s2)
# Store occurrence of it in s1
count_in_s1 = 0
# Find count of that character
# in the s1
for i in range(len(s1)):
# Increment count by 1 if
# that unique character is
# same as current character
if (s1[i] == s2[0]):
count_in_s1 += 1
# If count count_in_s1 is
# less than count_in_s2, then
# prs1 and return
if (count_in_s1 < count_in_s2):
print (s1, end = "")
return
# Otherwise, there is no
# possible arrangement
print (-1, end = "")
else:
# Checks if any character in
# s2 is less than its next
# character
inc = 1
# Iterate the string, s2
for i in range(len(s2) - 1):
# If s[i] is greater
# than the s[i+1]
if (s2[i] > s2[i + 1]):
# Set inc to 0
inc = 0
# If inc=1, prs1 in
# decreasing order
if (inc == 1):
s1 = sorted(s1)[::-1]
print ("".join(s1), end = "")
# Otherwise, prs1 in
# increasing order
else:
s1 = sorted(s1)
print ("".join(s1), end = "")
# Driver code
if __name__ == '__main__':
s1, s2 = "abcd", "ab"
rearrangeString(s1, s2)
# This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
class GFG
{
// Function to rearrange characters
// in string S1 such that S2 is not
// a subsequence of it
static void rearrangeString(char[] s1, char[] s2)
{
// Store the frequencies of
// characters of string s2
int[] cnt = new int[26];
// Traverse the string s2
for (int i = 0; i < s2.Length; i++)
// Update the frequency
cnt[s2[i] - 'a']++;
// Find the number of unique
// characters in s2
int unique = 0;
for (int i = 0; i < 26; i++)
// Increment unique by 1 if the
// condition satisfies
if (cnt[i] != 0)
unique++;
// Check if the number of unique
// characters in string s2 is 1
if (unique == 1) {
// Store the unique character
// frequency
int count_in_s2 = s2.Length;
// Store occurrence of it in s1
int count_in_s1 = 0;
// Find count of that character
// in the string s1
for (int i = 0; i < s1.Length; i++)
// Increment count by 1 if
// that unique character is
// same as current character
if (s1[i] == s2[0])
count_in_s1++;
// If count count_in_s1 is
// less than count_in_s2, then
// print s1 and return
if (count_in_s1 < count_in_s2) {
Console.Write(new string(s1));
return;
}
// Otherwise, there is no
// possible arrangement
Console.Write(-1);
}
else {
// Checks if any character in
// s2 is less than its next
// character
int inc = 1;
// Iterate the string, s2
for (int i = 0; i < s2.Length - 1; i++)
// If s[i] is greater
// than the s[i+1]
if (s2[i] > s2[i + 1])
// Set inc to 0
inc = 0;
// If inc=1, print s1 in
// decreasing order
if (inc == 1) {
Array.Sort(s1);
Array.Reverse(s1);
Console.Write(new string(s1));
}
// Otherwise, print s1 in
// increasing order
else {
Array.Sort(s1);
Console.Write(new string(s1));
}
}
}
// Driver code
static void Main() {
char[] s1 = "abcd".ToCharArray();
char[] s2 = "ab".ToCharArray();
rearrangeString(s1, s2);
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// Javascript program for the above approach
// Function to rearrange characters
// in string S1 such that S2 is not
// a subsequence of it
function rearrangeString(s1, s2)
{
// Store the frequencies of
// characters of string s2
let cnt = new Array(26);
cnt.fill(0);
// Traverse the string s2
for (let i = 0; i < s2.length; i++)
// Update the frequency
cnt[s2[i].charCodeAt() -
'a'.charCodeAt()]++;
// Find the number of unique
// characters in s2
let unique = 0;
for (let i = 0; i < 26; i++)
// Increment unique by 1 if the
// condition satisfies
if (cnt[i] != 0)
unique++;
// Check if the number of unique
// characters in string s2 is 1
if (unique == 1) {
// Store the unique character
// frequency
let count_in_s2 = s2.length;
// Store occurrence of it in s1
let count_in_s1 = 0;
// Find count of that character
// in the string s1
for (let i = 0; i < s1.length; i++)
// Increment count by 1 if
// that unique character is
// same as current character
if (s1[i] == s2[0])
count_in_s1++;
// If count count_in_s1 is
// less than count_in_s2, then
// print s1 and return
if (count_in_s1 < count_in_s2) {
document.write(s1.join(""));
return;
}
// Otherwise, there is no
// possible arrangement
document.write(-1);
}
else {
// Checks if any character in
// s2 is less than its next
// character
let inc = 1;
// Iterate the string, s2
for (let i = 0; i < s2.length - 1; i++)
// If s[i] is greater
// than the s[i+1]
if (s2[i].charCodeAt() >
s2[i + 1].charCodeAt())
// Set inc to 0
inc = 0;
// If inc=1, print s1 in
// decreasing order
if (inc == 1) {
s1.sort();
s1.reverse();
document.write(s1.join(""));
}
// Otherwise, print s1 in
// increasing order
else {
s1.sort();
document.write(s1.join(""));
}
}
}
let s1 = "abcd".split('');
let s2 = "ab".split('');
rearrangeString(s1, s2);
</script>
Producción:
dcba
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por single__loop y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA