Recuento de substrings en una string binaria que contiene más 1 que 0

Dada una string binaria s , la tarea es calcular el número de tales substrings donde el conteo de 1 es estrictamente mayor que el conteo de 0 . 

Ejemplos

Entrada: S = “110011”
Salida: 11
Explicación: Las 
substrings en las que el recuento de 1 es estrictamente mayor que el recuento de 0 son { S[0]}, {S[0], S[1]}, {S[ 0], S[2]}, {S[0], S[4]}, {S[0], S[5]}, {S[1], S[1]}, {S[1] , S[5]}, {S[3], S[5]}, {S[4], S[4]}, {S[4], S[5]}, {S[5], S [5]}.

Entrada: S = “101”
Salida: 3

Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todas las substrings y contar el número de 1 y 0 en cada substring. Aumente el conteo de aquellas substrings que contienen el conteo de 1 s mayor que el conteo de 0 s. Finalmente, imprima el conteo obtenido.
Complejidad de Tiempo : O(N ³ )
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar utilizando el algoritmo Merge Sort . Siga los pasos a continuación:

• Inicialice una array, digamos nums[] de tamaño n, donde n es la longitud de la string .
• Atraviesa la cuerda . Si s[i] == ‘1’ , entonces almacene 1 en nums[i] . De lo contrario, establezca nums[i] = -1 .
• Actualice pref[] para almacenar la suma de prefijos de la array nums[] .
• Ahora, el problema se reduce a contar el número de pares (i, j) en el arreglo pref[] , donde pref[i] < pref[j] e i < j , que es similar a contar inversiones en un arreglo desde atrás lado.
• Devuelve el número de inversiones de la array de suma de prefijos como la respuesta final.

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 merge two partitions
// such that the merged array is sorted
void merge(vector<int>& v, int left,
           int mid, int right, int& inversions)
{
    vector<int> temp(right - left + 1);
 
    int i = left;
    int j = mid + 1;
    int k = 0;
    int cnt = 0;
 
    while (i <= mid && j <= right) {
        if (v[i] <= v[j]) {
            temp[k++] = v[i++];
        }
        else {
            // Counting inversions
            inversions += (mid - i + 1);
 
            temp[k++] = v[j++];
        }
    }
 
    while (i <= mid)
        temp[k++] = v[i++];
 
    while (j <= right)
        temp[k++] = v[j++];
 
    k = 0;
    for (int a = left; a <= right; a++) {
        v[a] = temp[k++];
    }
}
 
// Function to implement merge sort
void mergeSort(vector<int>& v, int left,
               int right, int& inversions)
{
    if (left < right) {
        int mid = (left + right) / 2;
 
        mergeSort(v, left, mid, inversions);
        mergeSort(v, mid + 1, right, inversions);
        merge(v, left, mid, right, inversions);
    }
}
 
// Function to calculate number of
// inversions in a given array
int CountInversions(vector<int>& v)
{
    int n = v.size();
    int inversions = 0;
 
    // Calculate the number of inversions
    mergeSort(v, 0, n - 1, inversions);
 
    // Return the number of inversions
    return inversions;
}
 
// Function to count the number of
// substrings that contains more 1s than 0s
int getSubsCount(string& input)
{
    int n = input.length();
 
    vector<int> nums(n);
 
    for (int i = 0; i < n; i++) {
        nums[i] = input[i] - '0';
 
        if (nums[i] == 0)
            nums[i] = -1;
    }
 
    // Stores the prefix sum array
    vector<int> pref(n);
 
    int sum = 0;
 
    for (int i = 0; i < n; i++) {
        sum += nums[i];
        pref[i] = sum;
    }
 
    int cnt = 0;
 
    // Stores the count of valid substrings
    for (int i = 0; i < n; i++) {
        if (pref[i] > 0)
            cnt++;
    }
 
    reverse(pref.begin(), pref.end());
 
    int inversions = CountInversions(pref);
 
    int ans = cnt + inversions;
 
    return ans;
}
 
// Driver Code
int main()
{
 
    // Given Input
    string input = "101";
 
    // Function Call
    int ans = getSubsCount(input);
 
    cout << ans << endl;
 
    return 0;
}

# python 3 program for the above approach
 
# Function to merge two partitions
# such that the merged array is sorted
def merge(v, left,mid, right, inversions):
    temp = [0 for i in range(right - left + 1)]
 
    i = left
    j = mid + 1
    k = 0
    cnt = 0
 
    while (i <= mid and j <= right):
        if (v[i] <= v[j]):
            temp[k] = v[i]
            k += 1
            i += 1
 
        else:
            # Counting inversions
            inversions += (mid - i + 1)
 
            temp[k] = v[j]
            k += 1
            j += 1
 
    while (i <= mid):
        temp[k] = v[i]
        k += 1
        i += 1
 
    while (j <= right):
        temp[k] = v[j]
        k += 1
        j += 1
 
    k = 0
    for a in range(left,right+1,1):
        v[a] = temp[k]
        k += 1
 
# Function to implement merge sort
def mergeSort(v, left, right,inversions):
    if (left < right):
        mid = (left + right) // 2
 
        mergeSort(v, left, mid, inversions)
        mergeSort(v, mid + 1, right, inversions)
        merge(v, left, mid, right, inversions)
 
# Function to calculate number of
# inversions in a given array
def CountInversions(v):
    n = len(v)
    inversions = 0
 
    # Calculate the number of inversions
    mergeSort(v, 0, n - 1, inversions)
 
    # Return the number of inversions
    return inversions
 
# Function to count the number of
# substrings that contains more 1s than 0s
def getSubsCount(input):
    n = len(input)
 
    nums = [0 for i in range(n)]
 
    for i in range(n):
        nums[i] = ord(input[i]) - 48
 
        if (nums[i] == 0):
            nums[i] = -1
 
    # Stores the prefix sum array
    pref = [0 for i in range(n)]
 
    sum = 0
 
    for i in range(n):
        sum += nums[i]
        pref[i] = sum
 
    cnt = 0
 
    # Stores the count of valid substrings
    for i in range(n):
        if (pref[i] > 0):
            cnt += 1
     
    pref = pref[:-1]
 
    inversions = CountInversions(pref)
 
    ans = cnt + inversions + 1
 
    return ans
 
# Driver Code
if __name__ == '__main__':
   
    # Given Input
    input = "101"
 
    # Function Call
    ans = getSubsCount(input)
    print(ans)
     
    # This code is contributed by ipg2016107.

// C# program of the above approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
  // Function to merge two partitions
  // such that the merged array is sorted
  static void merge(int[] v, int left,
                    int mid, int right, int inversions)
  {
    int[] temp = new int[(right - left + 1)];
 
    int i = left;
    int j = mid + 1;
    int k = 0;
 
    while (i <= mid && j <= right) {
      if (v[i] <= v[j]) {
        temp[k++] = v[i++];
      }
      else {
        // Counting inversions
        inversions += (mid - i + 1);
 
        temp[k++] = v[j++];
      }
    }
 
    while (i <= mid)
      temp[k++] = v[i++];
 
    while (j <= right)
      temp[k++] = v[j++];
 
    k = 0;
    for (int a = left; a <= right; a++) {
      v[a] = temp[k++];
    }
  }
 
  // Function to implement merge sort
  static void mergeSort(int[] v, int left,
                        int right, int inversions)
  {
    if (left < right) {
      int mid = (left + right) / 2;
 
      mergeSort(v, left, mid, inversions);
      mergeSort(v, mid + 1, right, inversions);
      merge(v, left, mid, right, inversions);
    }
  }
 
  // Function to calculate number of
  // inversions in a given array
  static int CountInversions(int[] v)
  {
    int n = v.Length;
    int inversions = 0;
 
    // Calculate the number of inversions
    mergeSort(v, 0, n - 1, inversions);
 
    // Return the number of inversions
    return inversions;
  }
 
  // Function to count the number of
  // substrings that contains more 1s than 0s
  static int getSubsCount(string input)
  {
    int n = input.Length;
 
    int[] nums = new int[n];
 
    for (int i = 0; i < n; i++) {
      nums[i] = input[i] - '0';
 
      if (nums[i] == 0)
        nums[i] = -1;
    }
 
    // Stores the prefix sum array
    int[] pref = new int[n];
 
    int sum = 0;
 
    for (int i = 0; i < n; i++) {
      sum += nums[i];
      pref[i] = sum;
    }
 
    int cnt = 1;
 
    // Stores the count of valid substrings
    for (int i = 0; i < n; i++) {
      if (pref[i] > 0)
        cnt++;
    }
    Array.Sort(pref);
    Array.Reverse(pref);
 
    int inversions = CountInversions(pref);
 
    int ans = cnt + inversions;
 
    return ans;
  }
 
  // Driver Code
  public static void Main()
  {
    // Given Input
    string input = "101";
 
    // Function Call
    int ans = getSubsCount(input);
 
    Console.Write(ans);
  }
}
 
// This code is contributed by sanjoy_62.

<script>
// JavaScript program for the above approach
function merge(v, left, mid, right, inversions)
{
    var temp = new Array(right - left + 1).fill(0);
 
    var i = left;
    var j = mid + 1;
    var k = 0;
    var cnt = 0;
 
    while (i <= mid && j <= right) {
        if (v[i] <= v[j]) {
            temp[k] = v[i];
            k += 1;
            i += 1;
        } else {
            inversions += (mid - i + 1);
            temp[k] = v[j];
            k += 1;
            j += 1;
        }
 
    }
 
    while (i <= mid) {
        temp[k] = v[i];
        k += 1;
        i += 1;
    }
 
    while (j <= right) {
        temp[k] = v[j];
        k += 1;
        j += 1;
    }
    k = 0;
    for (var a = left; a <= right; a++) {
        v[a] = temp[k];
        k += 1;
    }
}
 
function mergeSort(v, left, right, inversions) {
    if (left < right) {
        var mid = Math.floor((left + right) / 2);
 
        mergeSort(v, left, mid, inversions);
        mergeSort(v, mid + 1, right, inversions);
        merge(v, left, mid, right, inversions);
    }
}
 
function CountInversions(v) {
    var n = v.length;
    var inversions = 0
 
    // Calculate the number of inversions
    mergeSort(v, 0, n - 1, inversions);
 
    return inversions;
}
 
function getSubsCount(input) {
    var n = input.length;
 
    var nums = new Array(n).fill(0);
 
    for (var i = 0; i < n; i++) {
        nums[i] = (input[i]).charCodeAt(0) - 48;
 
        if (nums[i] == 0)
            nums[i] = -1;
    }
 
    // Stores the prefix sum array
    var pref = new Array(n).fill(0);
    var sum = 0;
 
    for (var i = 0; i < n; i++) {
        sum += nums[i];
        pref[i] = sum;
    }
 
    var cnt = 0;
 
    // Stores the count of valid substrings
    for (var i = 0; i < n; i++) {
        if (pref[i] > 0)
            cnt += 1;
    }
 
    pref.pop();
    var inversions = CountInversions(pref);
    var ans = cnt + inversions + 1;
    return ans;
}
 
// Driver Code
var input = "101";
var ans = getSubsCount(input);
document.write(ans);
 
// This code is contributed by phasing17.
</script>

// Java program of the above approach
 
import java.util.*;
 
public class GFG {
 
    // Function to merge two partitions
    // such that the merged array is sorted
    static void merge(int[] v, int left, int mid, int right,
                      int inversions)
    {
        int[] temp = new int[(right - left + 1)];
 
        int i = left;
        int j = mid + 1;
        int k = 0;
 
        while ((i <= mid) && (j <= right)) {
            if (v[i] <= v[j]) {
                temp[k++] = v[i++];
            }
            else {
                // Counting inversions
                inversions += (mid - i + 1);
 
                temp[k++] = v[j++];
            }
        }
 
        while (i <= mid)
            temp[k++] = v[i++];
 
        while (j <= right)
            temp[k++] = v[j++];
 
        k = 0;
        for (int a = left; a <= right; a++) {
            v[a] = temp[k++];
        }
    }
 
    // Function to implement merge sort
    static void mergeSort(int[] v, int left, int right,
                          int inversions)
    {
        if (left < right) {
            int mid = (left + right) / 2;
 
            mergeSort(v, left, mid, inversions);
            mergeSort(v, mid + 1, right, inversions);
            merge(v, left, mid, right, inversions);
        }
    }
 
    // Function to calculate number of
    // inversions in a given array
    static int CountInversions(int[] v)
    {
        int n = v.length;
        int inversions = 0;
 
        // Calculate the number of inversions
        mergeSort(v, 0, n - 1, inversions);
 
        // Return the number of inversions
        return inversions;
    }
 
    // Function to count the number of
    // substrings that contains more 1s than 0s
    static int getSubsCount(String input)
    {
        int n = input.length();
 
        int[] nums = new int[n];
 
        for (int i = 0; i < n; i++) {
            nums[i] = input.charAt(i) - '0';
 
            if (nums[i] == 0)
                nums[i] = -1;
        }
 
        // Stores the prefix sum array
        int[] pref = new int[n];
 
        int sum = 0;
 
        for (int i = 0; i < n; i++) {
            sum += nums[i];
            pref[i] = sum;
        }
 
        int cnt = 1;
 
        // Stores the count of valid substrings
        for (int i = 0; i < n; i++) {
            if (pref[i] > 0)
                cnt++;
        }
        Arrays.sort(pref);
        Collections.reverse(Arrays.asList(pref));
 
        int inversions = CountInversions(pref);
 
        int ans = cnt + inversions;
 
        return ans;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given Input
        String input = "101";
 
        // Function Call
        int ans = getSubsCount(input);
 
        System.out.println(ans);
    }
}
 
// This code is contributed by phasing17.

3

Complejidad temporal: O(NlogN)
Espacio auxiliar: O(N)