Dada una string binaria S de longitud N . La tarea es encontrar lo siguiente:
- El número mínimo de subsecuencias en las que se puede dividir la string S , de modo que la subsecuencia no contenga ceros ni unos adyacentes.
- Número de subsecuencia al que pertenece cada carácter de la string S.
Si hay muchas respuestas, envíe cualquiera.
Ejemplos:
Entrada: S = “0011”, N = 4
Salida:
2
1 2 2 1
Explicación:
Puede haber un mínimo de 2 subsecuencias tales que no tengan ceros ni unos adyacentes.
Subsecuencia 1: «01»
Subsecuencia 2: «01»
Además, el primer carácter de S(‘0’) pertenece a la subsecuencia 1 («01»)
El segundo carácter de S(‘0’) pertenece a la subsecuencia 2 («01» )
El tercer carácter de S(‘1’) pertenece a la subsecuencia 2(“01”)
El cuarto carácter de S(‘1’) pertenece a la subsecuencia 1(“01”)Entrada: S = “1000110”, N = 7
Salida:
3
1 1 2 3 3 2 2
Enfoque: Cabe señalar que una subsecuencia es una secuencia que se puede derivar de la secuencia dada eliminando cero o más elementos sin cambiar el orden de los elementos restantes. Ahora, siga los pasos a continuación para resolver el problema:
- Cree un vector ans para almacenar las subsecuencias a las que pertenece cada carácter de la string S.
- Además, cree dos vectores endZero y endOne para almacenar las subsecuencias que terminan en ‘0’ y ‘1’ respectivamente.
- Como no puede haber ceros o unos adyacentes en una subsecuencia. Por lo tanto, si un carácter es ‘0’ , el siguiente carácter a colocar en la subsecuencia debe ser ‘1’ y viceversa.
- Ahora, usando un recorrido de bucle sobre cada carácter de S y verifique si es ‘0’ o ‘1’ . Además, declare una variable newSeq que represente la nueva subsecuencia que se formará si se encuentran ceros o unos consecutivos.
- Si un carácter es ‘0’ , verifique si el vector endOne está vacío o no:
- Si está vacío, inserte newSeq en endZero .
- De lo contrario, coloque la última subsecuencia de endOne en newSeq . Ahora, esta última subsecuencia de endOne ya no termina con ‘1’ ya que se le ha agregado ‘0’ . Por lo tanto, empújelo en endZero .
- De manera similar, si un carácter en S es ‘1’ , se siguen los mismos pasos anteriores, es decir, se verifica si el vector endZero está vacío o no:
- Si está vacío, inserte newSeq en endOne .
- De lo contrario, coloque la última subsecuencia de endZero en newSeq . Ahora, esta última subsecuencia de endZero ya no termina con ‘0’ ya que se le ha agregado ‘1’ . Por lo tanto, empújelo en endOne .
- Luego, inserte newSeq en el vector ans .
- Repita los pasos anteriores para cada carácter de S .
- El número mínimo de subsecuencias vendrá dado por la suma de los tamaños de endZero y endOne .
- Finalmente, genera el número mínimo de subsecuencias y el vector ans .
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 minimum number of
// subsequences into which S has to divide
// and the subsequences to which each character
// of S belongs to.
void findSeq(string S, int N)
{
// Stores the subsequences to which each
// character of S belongs to.
vector<int> ans(N);
// Store the subsequences ending with zeroes
// and ones respectively.
vector<int> endZero, endOne;
// Loop to traverse each character of S
for (int i = 0; i < N; ++i) {
// Stores the number of new
// subsequence to be formed
int newSeq = endZero.size()
+ endOne.size();
// If the character is '0'
if (S[i] == '0') {
// If there is no string
// which ends with '1'
if (endOne.empty()) {
// Push newSeq into endZero
endZero.push_back(newSeq);
}
else {
// Put the last element
// of endOne into newSeq
newSeq = endOne.back();
// Remove the last
// element of endOne
endOne.pop_back();
// newSeq ends with '0'
endZero.push_back(newSeq);
}
}
else {
// If there is no string
// which ends with '0'
if (endZero.empty()) {
// Push newSeq into endOne
endOne.push_back(newSeq);
}
else {
// Put the last element
// of endZero into newSeq
newSeq = endZero.back();
// Remove the last element of endOne
endZero.pop_back();
// newSeq ends with '1'
endOne.push_back(newSeq);
}
}
// Put newSeq into vector ans
ans[i] = newSeq;
}
// Output the minimum
// number of subsequences
cout << endZero.size()
+ endOne.size()
<< endl;
// Output the subsequences
// to which each character
// of S belongs to
for (int i = 0; i < N; ++i) {
// Add 1 as the index starts from 0
cout << ans[i] + 1 << " ";
}
}
// Driver Code
int main()
{
// Given input
string S = "1000110";
int N = 7;
// Function Call
findSeq(S, N);
return 0;
}
Java
// Java program for the above approach
import java.util.ArrayList;
class GFG {
// Function to find the minimum number of
// subsequences into which S has to divide
// and the subsequences to which each character
// of S belongs to.
public static void findSeq(String S, int N)
{
// Stores the subsequences to which each
// character of S belongs to.
int[] ans = new int[N];
// Store the subsequences ending with zeroes
// and ones respectively.
ArrayList<Integer> endZero = new ArrayList<Integer>();
ArrayList<Integer> endOne = new ArrayList<Integer>();
// Loop to traverse each character of S
for (int i = 0; i < N; ++i) {
// Stores the number of new
// subsequence to be formed
int newSeq = endZero.size() + endOne.size();
// If the character is '0'
if (S.charAt(i) == '0') {
// If there is no string
// which ends with '1'
if (endOne.isEmpty()) {
// Push newSeq into endZero
endZero.add(newSeq);
} else {
// Put the last element
// of endOne into newSeq
newSeq = endOne.get(endOne.size() - 1);
// Remove the last
// element of endOne
endOne.remove(endOne.size() - 1);
// newSeq ends with '0'
endZero.add(newSeq);
}
} else {
// If there is no string
// which ends with '0'
if (endZero.isEmpty()) {
// Push newSeq into endOne
endOne.add(newSeq);
} else {
// Put the last element
// of endZero into newSeq
newSeq = endZero.get(endZero.size() - 1);
// Remove the last element of endOne
endZero.remove(endZero.size() - 1);
// newSeq ends with '1'
endOne.add(newSeq);
}
}
// Put newSeq into vector ans
ans[i] = newSeq;
}
// Output the minimum
// number of subsequences
System.out.println(endZero.size() + endOne.size());
// Output the subsequences
// to which each character
// of S belongs to
for (int i = 0; i < N; ++i) {
// Add 1 as the index starts from 0
System.out.print(ans[i] + 1 + " ");
}
}
// Driver Code
public static void main(String args[]) {
// Given input
String S = "1000110";
int N = 7;
// Function Call
findSeq(S, N);
}
}
// This code is contributed by gfgking.
Python3
# python program for the above approach # Function to find the minimum number of # subsequences into which S has to divide # and the subsequences to which each character # of S belongs to. def findSeq(S, N): # Stores the subsequences to which each # character of S belongs to. ans = [0 for _ in range(N)] # Store the subsequences ending with zeroes # and ones respectively. endZero = [] endOne = [] # Loop to traverse each character of S for i in range(0, N): # Stores the number of new # subsequence to be formed newSeq = len(endZero) + len(endOne) # If the character is '0' if (S[i] == '0'): # If there is no string # which ends with '1' if (len(endOne) == 0): # Push newSeq into endZero endZero.append(newSeq) else: # Put the last element # of endOne into newSeq newSeq = endOne[len(endOne) - 1] # Remove the last # element of endOne endOne.pop() # newSeq ends with '0' endZero.append(newSeq) else: # If there is no string # which ends with '0' if (len(endZero) == 0): # Push newSeq into endOne endOne.append(newSeq) else: # Put the last element # of endZero into newSeq newSeq = endZero[len(endZero) - 1] # Remove the last element of endOne endZero.pop() # newSeq ends with '1' endOne.append(newSeq) # Put newSeq into vector ans ans[i] = newSeq # Output the minimum # number of subsequences print(len(endZero) + len(endOne)) # Output the subsequences # to which each character # of S belongs to for i in range(0, N): # Add 1 as the index starts from 0 print(ans[i] + 1, end=" ") # Driver Code if __name__ == "__main__": # Given input S = "1000110" N = 7 # Function Call findSeq(S, N) # This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the minimum number of
// subsequences into which S has to divide
// and the subsequences to which each character
// of S belongs to.
public static void findSeq(String S, int N)
{
// Stores the subsequences to which each
// character of S belongs to.
int[] ans = new int[N];
// Store the subsequences ending with zeroes
// and ones respectively.
List<int> endZero = new List<int>();
List<int> endOne = new List<int>();
// Loop to traverse each character of S
for (int i = 0; i < N; ++i)
{
// Stores the number of new
// subsequence to be formed
int newSeq = endZero.Count + endOne.Count;
// If the character is '0'
if (S[i] == '0')
{
// If there is no string
// which ends with '1'
if (endOne.Count == 0)
{
// Push newSeq into endZero
endZero.Add(newSeq);
}
else
{
// Put the last element
// of endOne into newSeq
newSeq = endOne[endOne.Count - 1];
// Remove the last
// element of endOne
endOne.Remove(endOne.Count - 1);
// newSeq ends with '0'
endZero.Add(newSeq);
}
}
else
{
// If there is no string
// which ends with '0'
if (endZero.Count == 0)
{
// Push newSeq into endOne
endOne.Add(newSeq);
}
else
{
// Put the last element
// of endZero into newSeq
newSeq = endZero[endZero.Count - 1];
// Remove the last element of endOne
endZero.Remove(endZero.Count - 1);
// newSeq ends with '1'
endOne.Add(newSeq);
}
}
// Put newSeq into vector ans
ans[i] = newSeq;
}
// Output the minimum
// number of subsequences
Console.WriteLine(endZero.Count + endOne.Count);
// Output the subsequences
// to which each character
// of S belongs to
for (int i = 0; i < N; ++i)
{
// Add 1 as the index starts from 0
Console.Write(ans[i] + 1 + " ");
}
}
// Driver Code
public static void Main()
{
// Given input
String S = "1000110";
int N = 7;
// Function Call
findSeq(S, N);
}
}
// This code is contributed by gfgking.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find the minimum number of
// subsequences into which S has to divide
// and the subsequences to which each character
// of S belongs to.
function findSeq(S, N)
{
// Stores the subsequences to which each
// character of S belongs to.
let ans = new Array(N);
// Store the subsequences ending with zeroes
// and ones respectively.
let endZero = [], endOne = [];
// Loop to traverse each character of S
for (let i = 0; i < N; ++i) {
// Stores the number of new
// subsequence to be formed
let newSeq = endZero.length
+ endOne.length;
// If the character is '0'
if (S[i] == '0') {
// If there is no string
// which ends with '1'
if (endOne.length == 0) {
// Push newSeq into endZero
endZero.push(newSeq);
}
else {
// Put the last element
// of endOne into newSeq
newSeq = endOne[endOne.length - 1];
// Remove the last
// element of endOne
endOne.pop();
// newSeq ends with '0'
endZero.push(newSeq);
}
}
else {
// If there is no string
// which ends with '0'
if (endZero.length == 0) {
// Push newSeq into endOne
endOne.push(newSeq);
}
else {
// Put the last element
// of endZero into newSeq
newSeq = endZero[endZero.length - 1];
// Remove the last element of endOne
endZero.pop();
// newSeq ends with '1'
endOne.push(newSeq);
}
}
// Put newSeq into vector ans
ans[i] = newSeq;
}
// Output the minimum
// number of subsequences
document.write(endZero.length
+ endOne.length
+ '<br>');
// Output the subsequences
// to which each character
// of S belongs to
for (let i = 0; i < N; ++i) {
// Add 1 as the index starts from 0
document.write(ans[i] + 1 + " ");
}
}
// Driver Code
// Given input
let S = "1000110";
let N = 7;
// Function Call
findSeq(S, N);
// This code is contributed by Potta Lokesh
</script>
Producción
3 1 1 2 3 3 2 2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por anusha00466 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA