Dada una string binaria S de longitud N y un entero K , la tarea es encontrar el número máximo de substrings que no se superponen que se pueden obtener al dividirla según las siguientes condiciones:
- Cada substring de la string contiene K o K+1 número de 1 .
- Como máximo, K substrings consecutivas pueden contener el mismo número de 1
Nota: Si la string no contiene K o K + 1 número de unos, simplemente descuide esa substring.
Ejemplos:
Entrada: S = “110101000010011011011011000100000”, K = 2
Salida: 6
Explicación: La string dada se puede dividir en – [110], [10100], [00100110], [110], [110], [11000100000] por lo que la respuesta es 6Entrada: S = “0000010001001100000110101100110000”, K = 2
Salida: 5
Explicación: La string dada se puede dividir en – [000001000100], [1100000], [1101], [0110], [0110000] por lo que la respuesta es 5.Entrada: S = “11111111111”, K = 4
Salida : 2
Explicación: La string se puede dividir en [1111], [1111] y
La string restante se puede ignorar porque no contiene K números de 1.
Enfoque: este problema se puede resolver utilizando el enfoque Greedy que se basa en la siguiente idea:
Para maximizar el conteo de substrings dividiéndose de tal manera que tantas substrings tengan un conteo de ‘1’ como K .
Como no es posible dividir una string que tenga el mismo número de ‘1’ sucesivamente más de K veces, luego de dividir K substrings con un conteo de ‘1’ como K, divida una substring con un conteo de ‘1’ como K + 1.
Siga los pasos a continuación para implementar el enfoque discutido anteriormente:
- Iterar la string de i = 0 a N-1 :
- Siga agregando los caracteres en la substring actual hasta que la cuenta de 1 sea K .
- Si las K substrings consecutivas ya tenían el mismo número de substrings, avance y agregue un 1 más en la substring actual y comience una nueva substring.
- Incrementa el recuento del número de substrings.
- Si no es posible tener K número de 1, ignore esa substring.
- Devuelve el recuento final de substrings.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check the number of 1's
// in the given string
int check(string s)
{
int count = 0;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '1') {
count++;
}
}
return count;
}
// Function to find the minimum operations
// to make the array elements same
int MaxSplit(string s, int n, int k)
{
int times = 0;
int k2 = 0;
int ans = 0;
int y;
// Traversing the string
for (int i = 0; i < s.length(); i++) {
// Creating the substring
string x = s.substr(k2, i - k2);
// Checking the count of 1's in
// the substring
y = check(x);
// Checking whether the count of 1's
// equal to k
if (y == k) {
// If k successive substring
// with count of 1's equals to
// k are used then simply find
// 1 substring whose count of
// 1's is k+1
if (times == k) {
continue;
}
// Else add 1 to ans as we have
// the substring increase times.
else {
ans += 1;
k2 = i;
times++;
}
}
// If count of 1's is k+1 then
// split the string and add one
// to ans also set times to zero.
else if (y == k + 1) {
times = 0;
ans += 1;
k2 = i;
}
}
// Condition for checking whether
// we can take up the remaining string
if (y == k && y == k + 1 && y != 0) {
ans += 1;
}
return ans;
}
// Driver Code
int main()
{
string S = "11111111111";
int K = 4;
int N = S.length();
// Function call
cout << MaxSplit(S, N, K);
return 0;
}
Java
// Java program for above approach
import java.io.*;
class GFG {
// Function to check the number of 1's
// in the given string
public static int check(String s)
{
int count = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '1') {
count++;
}
}
return count;
}
// Function to find the minimum operations
// to make the array elements same
public static int MaxSplit(String s, int n, int k)
{
int times = 0;
int k2 = 0;
int ans = 0;
int y = 0;
// Traversing the string
for (int i = 0; i < s.length(); i++) {
// Creating the substring
String x = s.substring(k2, i);
// Checking the count of 1's in
// the substring
y = check(x);
// Checking whether the count of 1's
// equal to k
if (y == k) {
// If k successive substring
// with count of 1's equals to
// k are used then simply find
// 1 substring whose count of
// 1's is k+1
if (times == k) {
continue;
}
// Else add 1 to ans as we have
// the substring increase times.
else {
ans += 1;
k2 = i;
times++;
}
}
// If count of 1's is k+1 then
// split the string and add one
// to ans also set times to zero.
else if (y == k + 1) {
times = 0;
ans += 1;
k2 = i;
}
}
// Condition for checking whether
// we can take up the remaining string
if (y == k && y == k + 1 && y != 0) {
ans += 1;
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
String S = "11111111111";
int K = 4;
int N = S.length();
// Function call
System.out.print(MaxSplit(S, N, K));
}
}
// This code is contributed by Rohit Pradhan
Python3
# Python3 program for above approach # Function to check the number of 1's # in the given string def check(s): count = 0 for i in range(0, len(s)): if (s[i] == '1'): count += 1 return count # Function to find the minimum operations # to make the array elements same def MaxSplit(s, n, k): times = 0 k2 = 0 ans = 0 y = 0 # Traversing the string for i in range(0, len(s)): # Creating the substring x = s[k2: k2 + i - k2] # Checking the count of 1's in # the substring y = check(x) # Checking whether the count of 1's # equal to k if (y == k): # If k successive substring # with count of 1's equals to # k are used then simply find # 1 substring whose count of # 1's is k+1 if (times == k): continue # Else add 1 to ans as we have # the substring increase times. else: ans += 1 k2 = i times += 1 # If count of 1's is k+1 then # split the string and add one # to ans also set times to zero. elif (y == k + 1): times = 0 ans += 1 k2 = i # Condition for checking whether # we can take up the remaining string if (y == k and y == k + 1 and y != 0): ans += 1 return ans # Driver Code if __name__ == "__main__": S = "11111111111" K = 4 N = len(S) # Function call print(MaxSplit(S, N, K)) # This code is contributed by rakeshsahni
C#
// C# code to implement the approach
using System;
class GFG
{
// Function to check the number of 1's
// in the given string
public static int check(String s)
{
int count = 0;
for (int i = 0; i < s.Length; i++) {
if (s[i] == '1') {
count++;
}
}
return count;
}
// Function to find the minimum operations
// to make the array elements same
public static int MaxSplit(String s, int n, int k)
{
int times = 0;
int k2 = 0;
int ans = 0;
int y = 0;
// Traversing the string
for (int i = 0; i < s.Length; i++) {
// Creating the substring
String x = s.Substring(k2, i-k2);
// Checking the count of 1's in
// the substring
y = check(x);
// Checking whether the count of 1's
// equal to k
if (y == k) {
// If k successive substring
// with count of 1's equals to
// k are used then simply find
// 1 substring whose count of
// 1's is k+1
if (times == k) {
continue;
}
// Else add 1 to ans as we have
// the substring increase times.
else {
ans += 1;
k2 = i;
times++;
}
}
// If count of 1's is k+1 then
// split the string and add one
// to ans also set times to zero.
else if (y == k + 1) {
times = 0;
ans += 1;
k2 = i;
}
}
// Condition for checking whether
// we can take up the remaining string
if (y == k && y == k + 1 && y != 0) {
ans += 1;
}
return ans;
}
// Driver Code
public static void Main () {
String S = "11111111111";
int K = 4;
int N = S.Length;
// Function call
Console.WriteLine(MaxSplit(S, N, K));
}
}
// This code is contributed by jana_sayantan.
Javascript
<script>
// JS program for above approach
// Function to check the number of 1's
// in the given string
function check(s)
{
var count = 0;
for (var i = 0; i < s.length; i++) {
if (s[i] == '1') {
count++;
}
}
return count;
}
// Function to find the minimum operations
// to make the array elements same
function MaxSplit(s, n, k)
{
var times = 0;
var k2 = 0;
var ans = 0;
var y;
// Traversing the string
for (var i = 0; i < s.length; i++) {
// Creating the substring
var x = s.substr(k2, i - k2);
// Checking the count of 1's in
// the substring
y = check(x);
// Checking whether the count of 1's
// equal to k
if (y == k) {
// If k successive substring
// with count of 1's equals to
// k are used then simply find
// 1 substring whose count of
// 1's is k+1
if (times == k) {
continue;
}
// Else add 1 to ans as we have
// the substring increase times.
else {
ans += 1;
k2 = i;
times++;
}
}
// If count of 1's is k+1 then
// split the string and add one
// to ans also set times to zero.
else if (y == k + 1) {
times = 0;
ans += 1;
k2 = i;
}
}
// Condition for checking whether
// we can take up the remaining string
if (y == k && y == k + 1 && y != 0) {
ans += 1;
}
return ans;
}
// Driver Code
var S = "11111111111";
var K = 4;
var N = S.length;
// Function call
document.write(MaxSplit(S, N, K));
// This code is contributed by phasing17
</script>
Producción
2
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por prathamjha5683 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA