Contar substrings con el mismo número de 0, 1 y 2

Dada una string que consta solo de 0, 1 o 2, cuente la cantidad de substrings que tienen la misma cantidad de 0, 1 y 2.

Ejemplos: 

Input  :  str = “0102010”
Output :  2
Explanation : Substring str[2, 4] = “102” and 
              substring str[4, 6] = “201” has 
              equal number of 0, 1 and 2

Input : str = "102100211"
Output : 5

Una solución simple es iterar a través de todas las substrings de str y verificar si contienen 0,1 y 2 iguales o no. El número total de substrings de str es O(n ² ) la comprobación de cada substring para el conteo toma O(n) veces, por lo que el tiempo total necesario para resolver este problema es O(n ³ ) tiempo con un enfoque de fuerza bruta.

Una solución eficiente es realizar un seguimiento de los recuentos de 0, 1 y 2.  

Let zc[i] denotes number of zeros between index 1 and i
    oc[i] denotes number of ones between index 1 and i
    tc[i] denotes number of twos between index 1 and i
for substring str[i, j] to be counted in result we should have :
    zc[i] – zc[j-1] = oc[i] – oc[j-1] = tc[i] - tc[j-1]
we can write above relation as follows :
z[i] – o[i] = z[j-1] – o[j-1]    and
z[i] – t[i] = z[j-1] – t[j-1]

Las relaciones anteriores se pueden rastrear mientras se realiza un bucle en la string, en cada índice i calcularemos este par de diferencia y verificaremos cuántas veces ha ocurrido previamente este par de diferencia y agregaremos ese conteo a nuestro resultado, para realizar un seguimiento del par de diferencia anterior, hemos usado el mapa en el código a continuación. La complejidad de tiempo total de esta solución es O (n log n) considerando el hecho de que las operaciones de mapa , como la búsqueda y la inserción, toman O (Log n) tiempo. 

Implementación:

// C++ program to find substring with equal
// number of 0's, 1's and 2's
#include <bits/stdc++.h>
using namespace std;
 
// Method to count number of substring which
// has equal 0, 1 and 2
int getSubstringWithEqual012(string str)
{
    int n = str.length();
 
    // map to store, how many times a difference
    // pair has occurred previously
    map< pair<int, int>, int > mp;
    mp[make_pair(0, 0)] = 1;
 
    //  zc (Count of zeroes), oc(Count of 1s)
    //  and tc(count of twos)
    //  In starting all counts are zero
    int zc = 0, oc = 0, tc = 0;
 
    //  looping into string
    int res = 0;  // Initialize result
    for (int i = 0; i < n; ++i)
    {
        // increasing the count of current character
        if (str[i] == '0') zc++;
        else if (str[i] == '1') oc++;
        else tc++;  // Assuming that string doesn't contain
                    // other characters
 
        // making pair of differences (z[i] - o[i],
        // z[i] - t[i])
        pair<int, int> tmp = make_pair(zc - oc,
                                       zc - tc);
 
        // Count of previous occurrences of above pair
        // indicates that the subarrays forming from
        // every previous occurrence to this occurrence
        // is a subarray with equal number of 0's, 1's
        // and 2's
        res = res + mp[tmp];
 
        // increasing the count of current difference
        // pair by 1
        mp[tmp]++;
    }
 
    return res;
}
 
//  driver code to test above method
int main()
{
    string str = "0102010";
    cout << getSubstringWithEqual012(str) << endl;
    return 0;
}

// Java program to find substring with equal
// number of 0's, 1's and 2's
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Method to count number of substring which
    // has equal 0, 1 and 2
    private static int getSubstringWithEqual012(String str)
    {
 
        // map to store, how many times a difference
        // pair has occurred previously (key = diff1 *
        // diff2)
        HashMap<String, Integer> map = new HashMap<>();
        map.put("0*0", 1);
 
        //  zc (Count of zeroes), oc(Count of 1s)
        //  and tc(count of twos)
        //  In starting all counts are zero
        int zc = 0, oc = 0, tc = 0;
 
        int ans = 0;
 
        //  looping into string
        for (int i = 0; i < str.length(); i++) {
            // increasing the count of current character
            if (str.charAt(i) == '0')
                zc++;
            else if (str.charAt(i) == '1')
                oc++;
            else
                tc++;
 
            // making key of differences (z[i] - o[i],
            // z[i] - t[i])
            String key = (zc - oc) + "*" + (zc - tc);
            // Count of previous occurrences of above pair
            // indicates that the subarrays forming from
            // every previous occurrence to this occurrence
            // is a subarray with equal number of 0's, 1's
            // and 2's
            ans += map.getOrDefault(key, 0);
 
            map.put(key, map.getOrDefault(key, 0) + 1);
        }
        // increasing the count of current difference
        // pair by 1
        return ans;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Input
        String str = "0102010";
        System.out.println(getSubstringWithEqual012(str));
    }
}

# Python3 program to find substring with equal
# number of 0's, 1's and 2's
 
# Method to count number of substring which
# has equal 0, 1 and 2
def getSubstringWithEqual012(string):
    n = len(string)
 
    # map to store, how many times a difference
    # pair has occurred previously
    mp = dict()
    mp[(0, 0)] = 1
 
    # zc (Count of zeroes), oc(Count of 1s)
    # and tc(count of twos)
    # In starting all counts are zero
    zc, oc, tc = 0, 0, 0
 
    # looping into string
    res = 0 # Initialize result
    for i in range(n):
 
        # increasing the count of current character
        if string[i] == '0':
            zc += 1
        else if string[i] == '1':
            oc += 1
        else:
            tc += 1 # Assuming that string doesn't contain
                    # other characters
 
        # making pair of differences (z[i] - o[i],
        # z[i] - t[i])
        tmp = (zc - oc, zc - tc)
 
        # Count of previous occurrences of above pair
        # indicates that the subarrays forming from
        # every previous occurrence to this occurrence
        # is a subarray with equal number of 0's, 1's
        # and 2's
        if tmp not in mp:
            res += 0
        else:
            res += mp[tmp]
 
        # increasing the count of current difference
        # pair by 1
        if tmp in mp:
            mp[tmp] += 1
        else:
            mp[tmp] = 1
 
    return res
 
# Driver Code
if __name__ == "__main__":
    string = "0102010"
    print(getSubstringWithEqual012(string))
 
# This code is contributed by
# sanjeev2552

2

Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.