Recuento de substrings con proporciones iguales de 0 y 1 hasta el i-ésimo índice en una string binaria dada

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:

1. Cree dos arrays de prefijos para las apariciones de 0 y 1 , digamos pre0[] y pre1[] respectivamente.
2. 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.
3. 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++ 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 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.

# 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# 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.

<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>

1 2 1 1 1 2 

Complejidad temporal: O(nlogn)
Espacio auxiliar: O(n)