Dadas tres strings binarias a , b y c , cada una de las cuales tiene 2*N caracteres cada una, la tarea es encontrar una string que tenga casi 3*N caracteres tal que al menos dos de las tres strings dadas ocurran como una de las subsecuencias .
Ejemplos:
Entrada: a = “00”, b = “11”, c = “01”
Salida : “010”
Explicación: Las strings “00” y “01” son subsecuencias de la string “010” y no tiene más de 3* N caracteres. Además, “001”, “011” pueden ser las posibles respuestas.Entrada: a = “011001”, b = “111010”, c = “010001”
Salida: “ 011001010″
Explicación: Aquí, las tres strings dadas ocurren como subsecuencias de la string de salida.
Enfoque: El problema dado se puede resolver usando las siguientes observaciones:
- Se puede observar que según el Principio del Pigeonhole , debe existir un conjunto de dos strings tal que el carácter más frecuente en ambas strings sea el mismo y su frecuencia sea >=N .
- Por lo tanto, para dos strings de este tipo, se puede crear una string de N caracteres más frecuentes. Los otros N caracteres restantes de ambas strings se pueden agregar a la string respectivamente según el orden en que aparecen. Por lo tanto, el tamaño máximo de la string resultante será como máximo 3*N .
Por lo tanto, después de encontrar el conjunto de strings con el mismo elemento más frecuente, el resto se puede resolver utilizando el enfoque de dos puntos . Mantenga dos punteros, uno para cada string, y siga los pasos a continuación:
- Inicialmente, i = 0 y j = 0 , donde i representa la primera string s1 y j representa la segunda string s2 .
- Si s1[i] no es igual al carácter más frecuente, imprima s1[i] e incremente i .
- Si s2[j] no es igual al carácter más frecuente, imprima s2[i] e incremente j .
- Si tanto s1[i] como s2[j] representan el carácter más frecuente, imprima s1[i] e incremente tanto i como j .
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 most frequent
// character in the given string
char MostFrequent(string s)
{
// Stores the frequency of
// 0 and 1 respectively
int arr[] = { 0, 0 };
for (char ch : s) {
arr[ch - '0']++;
}
// Stores most frequent character
char result = arr[0] > arr[1] ? '0' : '1';
// Return Answer
return result;
}
// Function to find a Binary String of
// at most 3N characters having at least
// two of the given three strings of 2N
// characters as one of its subsequence
void findStr(string& a, string& b, string& c)
{
// Stores most frequent char
char freq;
// Stores the respective string
// with most frequent values
string s1, s2;
// Code to find the set of
// two strings with same
// most frequent characters
if (MostFrequent(a) == MostFrequent(b)) {
s1 = a;
s2 = b;
freq = MostFrequent(a);
}
else if (MostFrequent(a) == MostFrequent(c)) {
s1 = a;
s2 = c;
freq = MostFrequent(a);
}
else {
s1 = b;
s2 = c;
freq = MostFrequent(b);
}
// Pointer to iterate strings
int i = 0, j = 0;
// Traversal using the
// two-pointer approach
while (i < s1.size() && j < s2.size()) {
// if current character
// is not most frequent
while (i < s1.size() && s1[i] != freq) {
cout << s1[i++];
}
// if current character
// is not most frequent
while (j < s2.size() && s2[j] != freq) {
cout << s2[j++];
}
// If end of string is reached
if (i == s1.size() || j == s2.size())
break;
// If both string character
// are same as most frequent
if (s1[i] == s2[j]) {
cout << s1[i];
i++;
j++;
}
else {
cout << s1[i];
i++;
}
}
// Print leftover characters
// of the string s1
while (i < s1.size()) {
cout << s1[i++];
}
// Print leftover characters
// of the string s2
while (j < s2.size()) {
cout << s2[j++];
}
}
// Driver Code
int main()
{
string a, b, c;
a = "00";
b = "11";
c = "01";
findStr(a, b, c);
return 0;
}
Java
// Java program for the above approach
class GFG
{
// Function to find most frequent
// character in the given String
static char MostFrequent(String s)
{
// Stores the frequency of
// 0 and 1 respectively
int []arr = { 0, 0 };
for(char ch : s.toCharArray()) {
arr[ch - '0']++;
}
// Stores most frequent character
char result = arr[0] > arr[1] ? '0' : '1';
// Return Answer
return result;
}
// Function to find a Binary String of
// at most 3N characters having at least
// two of the given three Strings of 2N
// characters as one of its subsequence
static void findStr(String a, String b, String c)
{
// Stores most frequent char
char freq;
// Stores the respective String
// with most frequent values
String s1 = "", s2 = "";
// Code to find the set of
// two Strings with same
// most frequent characters
if (MostFrequent(a) == MostFrequent(b)) {
s1 = a;
s2 = b;
freq = MostFrequent(a);
}
else if (MostFrequent(a) == MostFrequent(c)) {
s1 = a;
s2 = c;
freq = MostFrequent(a);
}
else {
s1 = b;
s2 = c;
freq = MostFrequent(b);
}
// Pointer to iterate Strings
int i = 0, j = 0;
// Traversal using the
// two-pointer approach
while (i < s1.length()&& j < s2.length()) {
// if current character
// is not most frequent
while (i < s1.length() && s1.charAt(i) != freq) {
System.out.print(s1.charAt(i++));
}
// if current character
// is not most frequent
while (j < s2.length() && s2.charAt(j) != freq) {
System.out.print(s2.charAt(j++));
}
// If end of String is reached
if (i == s1.length()|| j == s2.length())
break;
// If both String character
// are same as most frequent
if (s1.charAt(i) == s2.charAt(j)) {
System.out.print(s1.charAt(i));
i++;
j++;
}
else {
System.out.print(s1.charAt(i));
i++;
}
}
// Print leftover characters
// of the String s1
while (i < s1.length()) {
System.out.print(s1.charAt(i++));
}
// Print leftover characters
// of the String s2
while (j < s2.length()) {
System.out.print(s2.charAt(j++));
}
}
// Driver Code
public static void main(String args[])
{
String a = "00";
String b = "11";
String c = "01";
findStr(a, b, c);
}
}
// This code is contributed Saurabh Jaiswal
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find most frequent
// character in the given string
static char MostFrequent(string s)
{
// Stores the frequency of
// 0 and 1 respectively
int []arr = { 0, 0 };
foreach (char ch in s) {
arr[ch - '0']++;
}
// Stores most frequent character
char result = arr[0] > arr[1] ? '0' : '1';
// Return Answer
return result;
}
// Function to find a Binary String of
// at most 3N characters having at least
// two of the given three strings of 2N
// characters as one of its subsequence
static void findStr(string a, string b, string c)
{
// Stores most frequent char
char freq;
// Stores the respective string
// with most frequent values
string s1 = "", s2 = "";
// Code to find the set of
// two strings with same
// most frequent characters
if (MostFrequent(a) == MostFrequent(b)) {
s1 = a;
s2 = b;
freq = MostFrequent(a);
}
else if (MostFrequent(a) == MostFrequent(c)) {
s1 = a;
s2 = c;
freq = MostFrequent(a);
}
else {
s1 = b;
s2 = c;
freq = MostFrequent(b);
}
// Pointer to iterate strings
int i = 0, j = 0;
// Traversal using the
// two-pointer approach
while (i < s1.Length && j < s2.Length) {
// if current character
// is not most frequent
while (i < s1.Length && s1[i] != freq) {
Console.Write(s1[i++]);
}
// if current character
// is not most frequent
while (j < s2.Length && s2[j] != freq) {
Console.Write(s2[j++]);
}
// If end of string is reached
if (i == s1.Length || j == s2.Length)
break;
// If both string character
// are same as most frequent
if (s1[i] == s2[j]) {
Console.Write(s1[i]);
i++;
j++;
}
else {
Console.Write(s1[i]);
i++;
}
}
// Print leftover characters
// of the string s1
while (i < s1.Length) {
Console.Write(s1[i++]);
}
// Print leftover characters
// of the string s2
while (j < s2.Length) {
Console.Write(s2[j++]);
}
}
// Driver Code
public static void Main()
{
string a = "00";
string b = "11";
string c = "01";
findStr(a, b, c);
}
}
// This code is contributed Samim Hossain Mondal.
Python3
# python3 program for the above approach
# Function to find most frequent
# character in the given string
def MostFrequent(s):
# Stores the frequency of
# 0 and 1 respectively
arr = [0, 0]
for ch in s:
arr[ord(ch) - ord('0')] += 1
# Stores most frequent character
result = '0' if arr[0] > arr[1] else '1'
# Return Answer
return result
# Function to find a Binary String of
# at most 3N characters having at least
# two of the given three strings of 2N
# characters as one of its subsequence
def findStr(a, b, c):
# Stores most frequent char
freq = ''
# Stores the respective string
# with most frequent values
s1, s2 = "", ""
# Code to find the set of
# two strings with same
# most frequent characters
if (MostFrequent(a) == MostFrequent(b)):
s1 = a
s2 = b
freq = MostFrequent(a)
elif (MostFrequent(a) == MostFrequent(c)):
s1 = a
s2 = c
freq = MostFrequent(a)
else:
s1 = b
s2 = c
freq = MostFrequent(b)
# Pointer to iterate strings
i, j = 0, 0
# Traversal using the
# two-pointer approach
while (i < len(s1) and j < len(s2)):
# if current character
# is not most frequent
while (i < len(s1) and s1[i] != freq):
print(s1[i], end="")
i += 1
# if current character
# is not most frequent
while (j < len(s2) and s2[j] != freq):
print(s2[j], end="")
j += 1
# If end of string is reached
if (i == len(s1) or j == len(s2)):
break
# If both string character
# are same as most frequent
if (s1[i] == s2[j]):
print(s1[i], end="")
i += 1
j += 1
else:
print(s1[i], end="")
i += 1
# Print leftover characters
# of the string s1
while (i < len(s1)):
print(s1[i], end="")
i += 1
# Print leftover characters
# of the string s2
while (j < len(s2)):
print(s2[j], end="")
j += 1
# Driver Code
if __name__ == "__main__":
a = "00"
b = "11"
c = "01"
findStr(a, b, c)
# This code is contributed by rakeshsahni
Javascript
<script>
// JavaScript code for the above approach
// Function to find most frequent
// character in the given string
function MostFrequent(s)
{
// Stores the frequency of
// 0 and 1 respectively
let arr = new Array(2).fill(0)
for (let i = 0; i < s.length; i++) {
let ch = s[i];
arr[ch.charCodeAt(0) - '0'.charCodeAt(0)]++;
}
// Stores most frequent character
let result = arr[0] > arr[1] ? '0' : '1';
// Return Answer
return result;
}
// Function to find a Binary String of
// at most 3N characters having at least
// two of the given three strings of 2N
// characters as one of its subsequence
function findStr(a, b, c)
{
// Stores most frequent char
let freq;
// Stores the respective string
// with most frequent values
let s1, s2;
// Code to find the set of
// two strings with same
// most frequent characters
if (MostFrequent(a) == MostFrequent(b)) {
s1 = a;
s2 = b;
freq = MostFrequent(a);
}
else if (MostFrequent(a) == MostFrequent(c)) {
s1 = a;
s2 = c;
freq = MostFrequent(a);
}
else {
s1 = b;
s2 = c;
freq = MostFrequent(b);
}
// Pointer to iterate strings
let i = 0, j = 0;
// Traversal using the
// two-pointer approach
while (i < s1.length && j < s2.length) {
// if current character
// is not most frequent
while (i < s1.length && s1[i] != freq) {
document.write(s1[i++]);
}
// if current character
// is not most frequent
while (j < s2.length && s2[j] != freq) {
document.write(s2[j++]);
}
// If end of string is reached
if (i == s1.length || j == s2.length)
break;
// If both string character
// are same as most frequent
if (s1[i] == s2[j]) {
document.write(s1[i]);
i++;
j++;
}
else {
document.write(s1[i]);
i++;
}
}
// Print leftover characters
// of the string s1
while (i < s1.length) {
document.write(s1[i++]);
}
// Print leftover characters
// of the string s2
while (j < s2.length) {
document.write(s2[j++]);
}
}
// Driver Code
let a, b, c;
a = "00";
b = "11";
c = "01";
findStr(a, b, c);
// This code is contributed by Potta Lokesh
</script>
Producción
011
Tiempo Complejidad : O(N)
Espacio Auxiliar : O(N)
Publicación traducida automáticamente
Artículo escrito por singhh3010 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA