Dada una string binaria S , la tarea es imprimir el número máximo de substrings con proporciones iguales de 0 y 1 hasta el i-ésimo índice desde el principio.
Ejemplos:
Entrada: S = “110001”
Salida: {1, 2, 1, 1, 1, 2}
Explicación: La string dada se puede dividir en las siguientes substrings iguales:
- Substrings válidas hasta el índice 0: “1”, posible no. de substrings = 1
- Substrings válidas hasta el índice 1: “1”, “B”, posible no. de substrings = 2
- Substrings válidas hasta el índice 2: “110”, posible no. de substrings = 1
- Substrings válidas hasta el índice 3: “1100”, posible no. de substrings = 1
- Substrings válidas hasta el índice 4: “11000”, posible no. de substrings = 1
- Substrings válidas hasta el índice 5: “1100”, “01”, posible no. de substrings = 2
Entrada: S = “010100001”
Salida: {1, 1, 1, 2, 1, 2, 1, 1, 3}
Enfoque: la tarea se puede resolver utilizando conceptos matemáticos y HashMap para almacenar las frecuencias de los pares. Siga los pasos a continuación para resolver el problema:
- Cree dos arrays de prefijos para las apariciones de 0 y 1 , digamos pre0[] y pre1[] respectivamente.
- Para cada prefijo, etiquételo con un par (a, b) donde a = frecuencia de ‘0’ yb = frecuencia de ‘1’ en este prefijo. Divide a y b por mcd(a, b) para obtener la forma más simple.
- Iterar sobre todos los prefijos y almacenar la respuesta para el prefijo como el número actual de ocurrencias de este par.
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 retuan a prefix array of
// equal partitions of the given string
// consisting of 0s and 1s
void equalSubstrings(string s)
{
// Length of the string
int n = s.size();
// Prefix arrays for 0s and 1s
int pre0[n] = { 0 }, pre1[n] = { 0 };
// If character at index 0 is 0
if (s[0] == '0') {
pre0[0] = 1;
}
// If character at index 0 is 1
else {
pre1[0] = 1;
}
// Filling the prefix arrays
for (int i = 1; i < n; i++) {
if (s[i] == '0') {
pre0[i] = pre0[i - 1] + 1;
pre1[i] = pre1[i - 1];
}
else {
pre0[i] = pre0[i - 1];
pre1[i] = pre1[i - 1] + 1;
}
}
// Vector to store the answer
vector<int> ans;
// Map to store the ratio
map<pair<int, int>, int> mp;
for (int i = 0; i < n; i++) {
// Find the gcd of pre0[i] and pre1[i]
int x = __gcd(pre0[i], pre1[i]);
// Converting the elements in
// simplest form
int l = pre0[i] / x, r = pre1[i] / x;
// Update the value in map
mp[{ l, r }]++;
// Store this in ans
ans.push_back(mp[{ l, r }]);
}
// Return the ans vector
for (auto i : ans)
cout << i << " ";
}
// Driver Code
int main()
{
string s = "001110";
equalSubstrings(s);
return 0;
}
Java
// Java program for the above approach
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
class GFG
{
// Function to retuan a prefix array of
// equal partitions of the given string
// consisting of 0s and 1s
public static void equalSubstrings(String s)
{
// Length of the string
int n = s.length();
// Prefix arrays for 0s and 1s
int[] pre0 = new int[n];
int[] pre1 = new int[n];
Arrays.fill(pre0, 0);
Arrays.fill(pre1, 0);
// If character at index 0 is 0
if (s.charAt(0) == '0') {
pre0[0] = 1;
}
// If character at index 0 is 1
else {
pre1[0] = 1;
}
// Filling the prefix arrays
for (int i = 1; i < n; i++) {
if (s.charAt(i) == '0') {
pre0[i] = pre0[i - 1] + 1;
pre1[i] = pre1[i - 1];
} else {
pre0[i] = pre0[i - 1];
pre1[i] = pre1[i - 1] + 1;
}
}
// Vector to store the answer
ArrayList<Integer> ans = new ArrayList<Integer>();
// Map to store the ratio
HashMap<String, Integer> mp = new HashMap<String, Integer>();
for (int i = 0; i < n; i++)
{
// Find the gcd of pre0[i] and pre1[i]
int x = __gcd(pre0[i], pre1[i]);
// Converting the elements in
// simplest form
int l = pre0[i] / x, r = pre1[i] / x;
String key = l + "," + r;
// Update the value in map
if (mp.containsKey(key))
mp.put(key, mp.get(key) + 1);
else
mp.put(key, 1);
// Store this in ans
ans.add(mp.get(key));
}
// Return the ans vector
for (int i : ans)
System.out.print(i + " ");
}
public static int __gcd(int a, int b) {
if (b == 0)
return a;
return __gcd(b, a % b);
}
// Driver Code
public static void main(String args[]) {
String s = "001110";
equalSubstrings(s);
}
}
// This code is contributed by gfgking.
Python3
# Python program for the above approach
def __gcd(a, b):
if (b == 0):
return a
return __gcd(b, a % b)
# Function to retuan a prefix array of
# equal partitions of the given string
# consisting of 0s and 1s
def equalSubstrings(s):
# Length of the string
n = len(s)
# Prefix arrays for 0s and 1s
pre0 = [0] * n
pre1 = [0] * n
# If character at index 0 is 0
if (s[0] == '0'):
pre0[0] = 1
# If character at index 0 is 1
else:
pre1[0] = 1
# Filling the prefix arrays
for i in range(1, n):
if (s[i] == '0'):
pre0[i] = pre0[i - 1] + 1
pre1[i] = pre1[i - 1]
else:
pre0[i] = pre0[i - 1]
pre1[i] = pre1[i - 1] + 1
# Vector to store the answer
ans = []
# Map to store the ratio
mp = {}
for i in range(n):
# Find the gcd of pre0[i] and pre1[i]
x = __gcd(pre0[i], pre1[i])
# Converting the elements in
# simplest form
l = pre0[i] // x
r = pre1[i] // x
# Update the value in map
if (f'[{l}, {r}]' in mp):
mp[f'[{l}, {r}]'] += 1
else:
mp[f'[{l}, {r}]'] = 1
# Store this in ans
ans.append(mp[f'[{l}, {r}]'])
# Return the ans vector
for i in ans:
print(i, end=" ")
# Driver Code
s = "001110"
equalSubstrings(s)
# This code is contributed by gfgking
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to retuan a prefix array of
// equal partitions of the given string
// consisting of 0s and 1s
public static void equalSubstrings(string s)
{
// Length of the string
int n = s.Length;
// Prefix arrays for 0s and 1s
int[] pre0 = new int[n];
int[] pre1 = new int[n];
// Arrays.fill(pre0, 0);
// Arrays.fill(pre1, 0);
// If character at index 0 is 0
if (s[0] == '0') {
pre0[0] = 1;
}
// If character at index 0 is 1
else {
pre1[0] = 1;
}
// Filling the prefix arrays
for (int i = 1; i < n; i++) {
if (s[i] == '0') {
pre0[i] = pre0[i - 1] + 1;
pre1[i] = pre1[i - 1];
}
else {
pre0[i] = pre0[i - 1];
pre1[i] = pre1[i - 1] + 1;
}
}
// Vector to store the answer
List<int> ans = new List<int>();
// Map to store the ratio
Dictionary<string, int> mp
= new Dictionary<string, int>();
for (int i = 0; i < n; i++) {
// Find the gcd of pre0[i] and pre1[i]
int x = __gcd(pre0[i], pre1[i]);
// Converting the elements in
// simplest form
int l = pre0[i] / x, r = pre1[i] / x;
string key = l + "," + r;
// Update the value in map
if (mp.ContainsKey(key))
mp[key] += 1;
else
mp[key] = 1;
// Store this in ans
ans.Add(mp[key]);
}
// Return the ans vector
foreach(int i in ans) Console.Write(i + " ");
}
public static int __gcd(int a, int b)
{
if (b == 0)
return a;
return __gcd(b, a % b);
}
// Driver Code
public static void Main(string[] args)
{
string s = "001110";
equalSubstrings(s);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript program for the above approach
const __gcd = (a, b) => {
if (b == 0) return a;
return __gcd(b, a % b)
}
// Function to retuan a prefix array of
// equal partitions of the given string
// consisting of 0s and 1s
const equalSubstrings = (s) => {
// Length of the string
let n = s.length;
// Prefix arrays for 0s and 1s
let pre0 = new Array(n).fill(0);
let pre1 = new Array(n).fill(0);
// If character at index 0 is 0
if (s[0] == '0') {
pre0[0] = 1;
}
// If character at index 0 is 1
else {
pre1[0] = 1;
}
// Filling the prefix arrays
for (let i = 1; i < n; i++) {
if (s[i] == '0') {
pre0[i] = pre0[i - 1] + 1;
pre1[i] = pre1[i - 1];
}
else {
pre0[i] = pre0[i - 1];
pre1[i] = pre1[i - 1] + 1;
}
}
// Vector to store the answer
ans = [];
// Map to store the ratio
mp = {};
for (let i = 0; i < n; i++) {
// Find the gcd of pre0[i] and pre1[i]
let x = __gcd(pre0[i], pre1[i]);
// Converting the elements in
// simplest form
let l = pre0[i] / x, r = pre1[i] / x;
// Update the value in map
if ([l, r] in mp) mp[[l, r]] += 1
else mp[[l, r]] = 1
// Store this in ans
ans.push(mp[[l, r]]);
}
// Return the ans vector
for (let i in ans)
document.write(`${ans[i]} `);
}
// Driver Code
let s = "001110";
equalSubstrings(s);
// This code is contributed by rakeshsahni
</script>
Producción
1 2 1 1 1 2
Complejidad temporal: O(nlogn)
Espacio auxiliar: O(n)