Recuento de substrings que se pueden formar sin usar la lista dada de caracteres

Dada una string str y una lista de caracteres L , la tarea es contar el número total de substrings de la string str sin usar los caracteres dados en la lista L.

Ejemplos:

Entrada: str = “abcd”, L[] = {‘a’, ‘b’, ‘t’, ‘q’} 
Salida: 3 
Explicación: 
Al ignorar los caracteres ‘a’ y ‘b’ de la string dada, queda la substring “cd”. 
Por lo tanto, el número total de substrings formado por “cd” por: 
(2 * (2 + 1)) / 2 = 3

Entrada: str = “abcpxyz”, L[] = {‘a’, ‘p’, ‘q’} 
Salida: 9 
Explicación: 
Al ignorar los caracteres ‘a’ y ‘p’ de la string dada, substrings “bc” y “xyz” quedan. 
Por lo tanto, el número total de substrings formadas por las substrings es: 
(2*(2+1))/2 + (3*(3+1))/2 = 3 + 6 = 9 

Enfoque: el número total de substrings para una string determinada de longitud N viene dado por la fórmula 

(N * (N + 1)) / 2

La idea es usar la fórmula anterior y seguir los pasos a continuación para calcular la respuesta: 

1. Atraviese la string str carácter por carácter.
2. Cuente el número de caracteres en los que no se encuentra un carácter de la lista L. Sea el conteo N
3. Una vez que se encuentra un carácter de L , calcule (N * (N + 1) / 2) y agréguelo a la respuesta y restablezca el conteo N a cero.

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

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the Number of sub-strings
// without using given character
int countSubstring(string& S, char L[], int& n)
{
    int freq[26] = { 0 }, ans = 0;
 
    // Mark the given characters in
    // the freq array
    for (int i = 0; i < n; i++) {
        freq[(int)(L[i] - 'a')] = 1;
    }
 
    // Count variable to store the count
    // of the characters until a character
    // from given L is encountered
    int count = 0;
 
    for (auto x : S) {
 
        // If a character from L is encountered,
        // then the answer variable is incremented by
        // the value obtained by using
        // the mentioned formula and count is set to 0
        if (freq[(int)(x - 'a')]) {
            ans += (count * count + count) / 2;
            count = 0;
        }
        else
            count++;
    }
 
    // For last remaining characters
    ans += (count * count + count) / 2;
 
    return ans;
}
 
// Driver code
int main()
{
 
    string S = "abcpxyz";
    char L[] = { 'a', 'p', 'q' };
    int n = sizeof(L) / sizeof(L[0]);
 
    cout << countSubstring(S, L, n);
 
    return 0;
}

// Java implementation of the above approach
import java.util.*;
 
class GFG
{
 
// Function to find the Number of sub-Strings
// without using given character
static int countSubString(char []S, char L[], int n)
{
    int []freq = new int[26];
    int ans = 0;
 
    // Mark the given characters in
    // the freq array
    for (int i = 0; i < n; i++)
    {
        freq[(int)(L[i] - 'a')] = 1;
    }
 
    // Count variable to store the count
    // of the characters until a character
    // from given L is encountered
    int count = 0;
 
    for (int x : S)
    {
 
        // If a character from L is encountered,
        // then the answer variable is incremented by
        // the value obtained by using
        // the mentioned formula and count is set to 0
        if (freq[(int)(x - 'a')] > 0)
        {
            ans += (count * count + count) / 2;
            count = 0;
        }
        else
            count++;
    }
 
    // For last remaining characters
    ans += (count * count + count) / 2;
 
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    String S = "abcpxyz";
    char L[] = { 'a', 'p', 'q' };
    int n = L.length;
 
    System.out.print(countSubString(S.toCharArray(), L, n));
}
}
 
// This code is contributed by Rajput-Ji

# Python3 implementation of the above approach
 
# Function to find the Number of sub-strings
# without using given character
def countSubstring(S, L,n):
    freq = [0 for i in range(26)]
     
    # the freq array
    for i in range(n):
        freq[(ord(L[i]) - ord('a'))] = 1
 
    # Count variable to store the count
    # of the characters until a character
    # from given L is encountered
    count,ans = 0,0
 
    for x in S:
 
        # If a character from L is encountered,
        # then the answer variable is incremented by
        # the value obtained by using
        # the mentioned formula and count is set to 0
        if (freq[ord(x) - ord('a')]):
            ans += (count * count + count) // 2
            count = 0
        else:
            count += 1
 
    # For last remaining characters
    ans += (count * count + count) // 2
 
    return ans
 
# Driver code
 
S = "abcpxyz"
L = ['a', 'p', 'q']
n = len(L)
 
print(countSubstring(S, L, n))
 
# This code is contributed by mohit kumar 29

// C# implementation of the above approach
using System;
 
class GFG
{
 
    // Function to find the Number of sub-Strings
    // without using given character
    static int countSubString(char []S, char []L, int n)
    {
        int []freq = new int[26];
        int ans = 0;
     
        // Mark the given characters in
        // the freq array
        for (int i = 0; i < n; i++)
        {
            freq[(int)(L[i] - 'a')] = 1;
        }
     
        // Count variable to store the count
        // of the characters until a character
        // from given L is encountered
        int count = 0;
     
        foreach (int x in S)
        {
     
            // If a character from L is encountered,
            // then the answer variable is incremented by
            // the value obtained by using
            // the mentioned formula and count is set to 0
            if (freq[(int)(x - 'a')] > 0)
            {
                ans += (count * count + count) / 2;
                count = 0;
            }
            else
                count++;
        }
     
        // For last remaining characters
        ans += (count * count + count) / 2;
     
        return ans;
    }
     
    // Driver code
    public static void Main()
    {
        string S = "abcpxyz";
        char []L = { 'a', 'p', 'q' };
        int n = L.Length;
     
        Console.WriteLine(countSubString(S.ToCharArray(), L, n));
    }
}
 
// This code is contributed by Yash_R

<script>
      // JavaScript implementation of the above approach
      // Function to find the Number of sub-Strings
      // without using given character
      function countSubString(S, L, n) {
        var freq = new Array(26).fill(0);
        var ans = 0;
 
        // Mark the given characters in
        // the freq array
        for (var i = 0; i < n; i++) {
          freq[L[i].charCodeAt(0) - "a".charCodeAt(0)] = 1;
        }
 
        // Count variable to store the count
        // of the characters until a character
        // from given L is encountered
        var count = 0;
 
        for (const x of S) {
          // If a character from L is encountered,
          // then the answer variable is incremented by
          // the value obtained by using
          // the mentioned formula and count is set to 0
          if (freq[x.charCodeAt(0) - "a".charCodeAt(0)] > 0) {
            ans = ans + parseInt((count * count + count) / 2);
            count = 0;
          } else count++;
        }
 
        // For last remaining characters
        ans += parseInt((count * count + count) / 2);
 
        return ans;
      }
 
      // Driver code
      var S = "abcpxyz";
      var L = ["a", "p", "q"];
      var n = L.length;
 
      document.write(countSubString(S.split(""), L, n));
</script>

9

Complejidad temporal: O(n + |S|)

Espacio Auxiliar: O(26)