Recuento de substrings de una string binaria que contiene solo 1s

Dada una string binaria de longitud N , necesitamos averiguar cuántas substrings de esta string contienen solo 1.

Ejemplos: 

Entrada: S = “0110111”
Salida: 9
Explicación:
Hay 9 substrings con solo caracteres de 1. 
“1” viene 5 veces. 
“11” viene 3 veces. 
«111» viene 1 vez.

Entrada: S = “000”
Salida: 0

Enfoque : la idea es atravesar la string binaria y contar los consecutivos en la string. A continuación se muestra la ilustración del enfoque:

• Atraviesa la string binaria dada desde el índice 0 hasta la longitud – 1
• Cuente el número de «1» consecutivos hasta el índice i.
• Por cada nuevo carácter str[i], habrá más substrings con todos los caracteres como “1”

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation to find
// count of substring containing
// only ones
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the total number
// of substring having only ones
int countOfSubstringWithOnlyOnes(string s)
{
    int res = 0, count = 0;
    for (int i = 0; i < s.length(); i++) {
    count = s[i] == '1' ? count + 1 : 0;
    res = (res + count);
    }
    return res;
}
 
// Driver Code
int main()
{
    string s = "0110111";
    cout << countOfSubstringWithOnlyOnes(s)
        << endl;
    return 0;
}

// Java implementation to find
// count of substring containing
// only ones
class GFG{
     
// Function to find the total number
// of substring having only ones
static int countOfSubstringWithOnlyOnes(String s)
{
    int res = 0, count = 0;
    for(int i = 0; i < s.length(); i++)
    {
        count = s.charAt(i) == '1' ? count + 1 : 0;
        res = (res + count);
    }
    return res;
}
 
// Driver code
public static void main(String[] args)
{
    String s = "0110111";
     
    System.out.println(countOfSubstringWithOnlyOnes(s));
}
}
 
// This code is contributed by dewantipandeydp

# Python3 implementation to find
# count of substring containing
# only ones
 
# Function to find the total number
# of substring having only ones
def countOfSubstringWithOnlyOnes(s):
 
    count = 0
    res = 0
     
    for i in range(0,len(s)):
        if s[i] == '1':
            count = count + 1
        else:
            count = 0;
             
        res = res + count
             
    return res
 
# Driver Code
s = "0110111"
print(countOfSubstringWithOnlyOnes(s))
 
# This code is contributed by jojo9911

// C# implementation to find count
// of substring containing only ones
using System;
 
class GFG{
     
// Function to find the total number
// of substring having only ones
static int countOfSubstringWithOnlyOnes(string s)
{
    int res = 0, count = 0;
     
    for(int i = 0; i < s.Length; i++)
    {
        count = s[i] == '1' ? count + 1 : 0;
        res = (res + count);
    }
    return res;
}
 
// Driver code
public static void Main(string[] args)
{
    string s = "0110111";
     
    Console.Write(countOfSubstringWithOnlyOnes(s));
}
}
 
// This code is contributed by rutvik_56

<script>
 
// Javascript implementation to find
// count of substring containing
// only ones
 
// Function to find the total number
// of substring having only ones
function countOfSubstringWithOnlyOnes(s)
{
    var res = 0, count = 0;
    for (var i = 0; i < s.length; i++) {
    count = s[i] == '1' ? count + 1 : 0;
    res = (res + count);
    }
    return res;
}
 
// Driver Code
var s = "0110111";
document.write( countOfSubstringWithOnlyOnes(s));
 
</script>

9

Complejidad de tiempo: O(n), donde n es el tamaño de la string dada
Espacio auxiliar: O(1)