Recuento de substrings que tienen una suma igual a su longitud

Dada una string numérica str , la tarea es calcular el número de substrings con la suma de dígitos igual a su longitud.

Ejemplos:

Entrada: str = “112112” 
Salida: 6 
Explicación: 
Las substrings “1”, “1”, “11”, “1”, “1”, “11” cumplen la condición dada.
Entrada: str = «1101112» 
Salida: 12

Enfoque ingenuo: la solución más simple es generar todas las substrings de la string dada y, para cada substring, verificar si su suma es igual a su longitud o no. Para cada substring que se encuentre verdadera, aumente el conteo. 
Complejidad de Tiempo: O(N ³ ) 
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar utilizando un Hashmap y seguir actualizando el recuento de substrings en el Hashmap e imprimir el recuento requerido al final.

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

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the number of
// substrings with sum equal to length
int countSubstrings(string s, int n)
{
 
    int count = 0, sum = 0;
 
    // Stores the count of substrings
    unordered_map<int, int> mp;
    mp[0]++;
 
    for (int i = 0; i < n; ++i) {
 
        // Add character to sum
        sum += (s[i] - '0');
 
        // Add count of substrings to result
        count += mp[sum - (i + 1)];
 
        // Increase count of subarrays
        ++mp[sum - (i + 1)];
    }
 
    // Return count
    return count;
}
 
// Driver Code
int main()
{
    string str = "112112";
    int n = str.length();
    cout << countSubstrings(str, n) << endl;
 
    return 0;
}

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
 
// Function to count the number of
// subStrings with sum equal to length
static int countSubStrings(String s, int n)
{
    int count = 0, sum = 0;
 
    // Stores the count of subStrings
    HashMap<Integer,
            Integer> mp = new HashMap<Integer,
                                      Integer>();
    mp.put(0, 1);
 
    for(int i = 0; i < n; ++i)
    {
         
        // Add character to sum
        sum += (s.charAt(i)- '0');
 
        // Add count of subStrings to result
        count += mp.containsKey(sum - (i + 1)) == true ?
                         mp.get(sum - (i + 1)) : 0;
 
        // Increase count of subarrays
        if(!mp.containsKey(sum - (i + 1)))
                    mp.put(sum - (i + 1), 1);
        else
            mp.put(sum - (i + 1),
            mp.get(sum - (i + 1)) + 1);
    }
 
    // Return count
    return count;
}
 
// Driver Code
public static void main(String[] args)
{
    String str = "112112";
    int n = str.length();
     
    System.out.print(countSubStrings(str, n) + "\n");
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program to implement
# the above approach
from collections import defaultdict
 
# Function to count the number of
# substrings with sum equal to length
def countSubstrings(s, n):
     
    count, sum = 0, 0
     
    # Stores the count of substrings
    mp = defaultdict(lambda : 0)
    mp[0] += 1
     
    for i in range(n):
         
        # Add character to sum
        sum += ord(s[i]) - ord('0')
         
        # Add count of substrings to result
        count += mp[sum - (i + 1)]
         
        # Increase count of subarrays
        mp[sum - (i + 1)] += 1
         
    # Return count
    return count
 
# Driver code
str = '112112'
n = len(str)
 
print(countSubstrings(str, n))
 
# This code is contributed by Stuti Pathak

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
 
// Function to count the number of
// subStrings with sum equal to length
static int countSubStrings(String s, int n)
{
    int count = 0, sum = 0;
 
    // Stores the count of subStrings
    Dictionary<int,
               int> mp = new Dictionary<int,
                                        int>();
    mp.Add(0, 1);
 
    for(int i = 0; i < n; ++i)
    {
         
        // Add character to sum
        sum += (s[i]- '0');
 
        // Add count of subStrings to result
        count += mp.ContainsKey(sum - (i + 1)) == true ?
                             mp[sum - (i + 1)] : 0;
 
        // Increase count of subarrays
        if(!mp.ContainsKey(sum - (i + 1)))
                    mp.Add(sum - (i + 1), 1);
        else
            mp[sum - (i + 1)] = mp[sum - (i + 1)] + 1;
    }
 
    // Return count
    return count;
}
 
// Driver Code
public static void Main(String[] args)
{
    String str = "112112";
    int n = str.Length;
     
    Console.Write(countSubStrings(str, n) + "\n");
}
}
 
// This code is contributed by Rohit_ranjan

<script>
 
// Javascript Program to implement
// the above approach
 
// Function to count the number of
// substrings with sum equal to length
function countSubstrings(s, n)
{
 
    var count = 0, sum = 0;
 
    // Stores the count of substrings
    var mp = new Map();
 
    if(mp.has(0))
        mp.set(0, mp.get(0)+1)
    else
        mp.set(0, 1);
 
    for (var i = 0; i < n; ++i) {
 
        // Add character to sum
        sum += (s[i].charCodeAt(0) - '0'.charCodeAt(0));
 
        // Add count of substrings to result
        if(mp.has(sum - (i + 1)))
            count += mp.get(sum - (i + 1));
 
        // Increase count of subarrays
        if(mp.has(sum - (i + 1)))
            mp.set(sum - (i + 1), mp.get(sum - (i + 1))+1)
        else
            mp.set(sum - (i + 1), 1)
    }
 
    // Return count
    return count;
}
 
// Driver Code
var str = "112112";
var n = str.length;
document.write( countSubstrings(str, n));
 
</script>

6

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