Conteo de substrings formadas usando un conjunto dado de caracteres solamente

Dada una string str y una array arr[] de K caracteres, la tarea es encontrar el número de substrings de str que contienen caracteres solo de la array de caracteres dada arr[] .

Nota: La string str y arr[] contienen solo letras en minúsculas.

Ejemplos:

Entrada: S = “abcb”, K = 2, charArray[] = {‘a’, ‘b’}
Salida: 4
Explicación:
Las substrings son “a”, “ab”, “b”, “b” usando el caracteres disponibles

Entrada: S = “aabdbbtr”, K = 4, charArray[] = {‘e’, ‘a’, ‘r’, ‘t’} Salida: 6
Explicación :
Las
substrings “a”, “aa”, “a ”, “t”, “tr”, “r” utilizando los caracteres disponibles.

Enfoque ingenuo: el enfoque ingenuo es generar todas las substrings posibles para la string dada str y verificar si cada substring consta de caracteres dados en la array arr[] o no. En caso afirmativo, cuente esa substring; de lo contrario, verifique la siguiente substring.

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(N)

Enfoque eficiente: el enfoque ingenuo anterior se puede optimizar, ya que eliminaremos el recuento de substrings formadas por caracteres que no están presentes en la array dada arr[] . A continuación se muestran los pasos:

• Almacene los caracteres presentes en la array arr[] en una array booleana de tamaño 26, de modo que la búsqueda de cualquier carácter se pueda realizar en tiempo O(1) .
• El número total de substrings formadas por una string de longitud N es (N*(N+1))/2 , inicialice la cuenta como (N*(N+1))/2 .
• Recorra la string de izquierda a derecha y almacene el índice del último carácter que encontramos en la string que no está presente en la array arr[] usando una variable lastPos
• Si mientras recorremos la string encontramos algún carácter que no está presente en arr[] , restamos el número de substrings que contendrán este carácter y tendrán un punto de inicio mayor que el valor de lastPos . Supongamos que estamos en el índice i, entonces el número de substrings a restar estará dado por

(i - lastPos)*(N - i)

• Actualice el valor de lastPos cada vez que encontremos un carácter no disponible en charArray[] .

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 find the number of
// substrings that can be formed
// using given characters
void numberofsubstrings(string str, int k,
                        char charArray[])
{
    int N = str.length();
 
    // Boolean array for storing
    // the available characters
    bool available[26] = { 0 };
 
    // Mark indices of all
    // available characters as 1
    for (int i = 0; i < k; i++) {
        available[charArray[i] - 'a'] = 1;
    }
 
    // Initialize lastPos as -1
    int lastPos = -1;
 
    // Initialize ans with the total
    // no of possible substrings
    int ans = (N * (N + 1)) / 2;
 
    // Traverse the string from
    // left to right
    for (int i = 0; i < N; i++) {
 
        // If the current character
        // is not present in B
        if (available[str[i] - 'a'] == 0) {
 
            // Subtract the total possible
            // substrings
            ans -= ((i - lastPos)
                    * (N - i));
 
            // Update the value of
            // lastpos to current index
            lastPos = i;
        }
    }
 
    // Print the final answer
    cout << ans << endl;
}
 
// Driver Code
int main()
{
    // Given String
    string str = "abcb";
    int k = 2;
 
    // Given character array
    char charArray[k] = { 'a', 'b' };
 
    // Function Call
    numberofsubstrings(str, k, charArray);
    return 0;
}

// Java program for the above approach
import java.util.Arrays;
 
class GFG{
     
// Function to find the number of
// substrings that can be formed
// using given characters
public static void numberofsubstrings(String str, int k,
                                      char charArray[])
{
    int N = str.length();
 
    // Boolean array for storing
    // the available characters
    int available[] = new int[26];
    Arrays.fill(available, 0);
 
    // Mark indices of all
    // available characters as 1
    for(int i = 0; i < k; i++)
    {
       available[charArray[i] - 'a'] = 1;
    }
 
    // Initialize lastPos as -1
    int lastPos = -1;
 
    // Initialize ans with the total
    // no of possible substrings
    int ans = (N * (N + 1)) / 2;
 
    // Traverse the string from
    // left to right
    for(int i = 0; i < N; i++)
    {
        
       // If the current character
       // is not present in B
       if (available[str.charAt(i) - 'a'] == 0)
       {
            
           // Subtract the total possible
           // substrings
           ans -= ((i - lastPos) * (N - i));
            
           // Update the value of
           // lastpos to current index
           lastPos = i;
       }
    }
     
    // Print the final answer
    System.out.println(ans);
}
 
// Driver Code
public static void main(String args[])
{
     
    // Given String
    String str = "abcb";
    int k = 2;
 
    // Given character array
    char []charArray = {'a', 'b'};
 
    // Function Call
    numberofsubstrings(str, k, charArray);
}
}
 
// This code is contributed by SoumikMondal

# Python3 program for the above approach
 
# Function to find the number of
# substrings that can be formed
# using given characters
def numberofsubstrings(str, k, charArray):
     
    N = len(str)
 
    # Boolean array for storing
    # the available characters
    available = [0] * 26
 
    # Mark indices of all
    # available characters as 1
    for i in range(0, k):
        available[ord(charArray[i]) -
                  ord('a')] = 1
     
    # Initialize lastPos as -1
    lastPos = -1
 
    # Initialize ans with the total
    # no of possible substrings
    ans = (N * (N + 1)) / 2
 
    # Traverse the string from
    # left to right
    for i in range(0, N):
 
        # If the current character
        # is not present in B
        if (available[ord(str[i]) -
                      ord('a')] == 0):
 
            # Subtract the total possible
            # substrings
            ans -= ((i - lastPos) * (N - i))
 
            # Update the value of
            # lastpos to current index
            lastPos = i
         
    # Print the final answer
    print(int(ans))
 
# Driver Code
 
# Given String
str = "abcb"
k = 2
 
# Given character array
charArray = [ 'a', 'b' ]
 
# Function call
numberofsubstrings(str, k, charArray)
 
# This code is contributed by sanjoy_62

// C# program for the above approach
using System;
 
class GFG{
     
// Function to find the number of
// substrings that can be formed
// using given characters
public static void numberofsubstrings(String str, int k,
                                      char []charArray)
{
    int N = str.Length;
 
    // Boolean array for storing
    // the available characters
    int []available = new int[26];
 
    // Mark indices of all
    // available characters as 1
    for(int i = 0; i < k; i++)
    {
       available[charArray[i] - 'a'] = 1;
    }
 
    // Initialize lastPos as -1
    int lastPos = -1;
 
    // Initialize ans with the total
    // no of possible substrings
    int ans = (N * (N + 1)) / 2;
 
    // Traverse the string from
    // left to right
    for(int i = 0; i < N; i++)
    {
        
       // If the current character
       // is not present in B
       if (available[str[i] - 'a'] == 0)
       {
 
           // Subtract the total possible
           // substrings
           ans -= ((i - lastPos) * (N - i));
            
           // Update the value of
           // lastpos to current index
           lastPos = i;
       }
    }
     
    // Print the final answer
    Console.WriteLine(ans);
}
 
// Driver Code
public static void Main(String []args)
{
     
    // Given String
    String str = "abcb";
    int k = 2;
 
    // Given character array
    char []charArray = {'a', 'b'};
 
    // Function Call
    numberofsubstrings(str, k, charArray);
}
}
 
// This code is contributed by Princi Singh

<script>
// JavaScript program for the above approach
 
// Function to find the number of
// substrings that can be formed
// using given characters
function numberofsubstrings(str, k, charArray)
{
    var N = str.length;
 
    // Boolean array for storing
    // the available characters
    var available = [ 26 ];
        
    // Mark indices of all
    // available characters as 1
    for(var i = 0; i < k; i++)
    {
    available[charArray[i] - 'a'] = 1;
    }
 
    // Initialize lastPos as -1
    var lastPos = -1;
 
    // Initialize ans with the total
    // no of possible substrings
    var ans = (N * (N + 1)) / 2;
 
    // Traverse the string from
    // left to right
    for(var i = 0; i < N; i++)
    {
         
    // If the current character
    // is not present in B
    if (available[str.charAt(i) - 'a'] == 0)
    {
             
        // Subtract the total possible
        // substrings
        ans -= ((i - lastPos) * (N - i));
             
        // Update the value of
        // lastpos to current index
        lastPos = i;
    }
    }
     
    // Print the final answer
    document.write(ans);
}
 
// Driver Code
    // Given String
    var str = "abcb";
    var k = 2;
 
    // Given character array
    var charArray = ['a', 'b'];
 
    // Function Call
    numberofsubstrings(str, k, charArray);
 
// This code is contributed by shivanisinghss2110.
 
</script>

4

Complejidad de tiempo: O(N) , N es la longitud de la string
Espacio auxiliar: O(1)