Recuento de substrings que contienen el carácter X al menos una vez

Dada una string str y un carácter X . La tarea es encontrar el número total de substrings que contienen el carácter X al menos una vez.
Ejemplos: 
 

Entrada: str = “abcd”, X = ‘b’ 
Salida: 6 
“ab”, “abc”, “abcd”, “b”, “bc” y “bcd” son las substrings requeridas.
Entrada: str = «geeksforgeeks», X = ‘e’ 
Salida: 66 
 

Enfoque: el número total de substrings es n * (n + 1) / 2 , entre ellas solo se deben contar las substrings que contienen el carácter X. El carácter X está presente en esas substrings desde la posición de X hasta la longitud de la string. Para cada carácter antes de X , se debe contar esta substring.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of
// required sub-strings
int countSubStr(string str, int n, char x)
{
    int res = 0, count = 0;
    for (int i = 0; i < n; i++) {
        if (str[i] == x) {
 
            // Number of sub-strings from position
            // of current x to the end of str
            res += ((count + 1) * (n - i));
 
            // To store the number of characters
            // before x
            count = 0;
        }
        else
            count++;
    }
 
    return res;
}
 
// Driver code
int main()
{
    string str = "abcabc";
    int n = str.length();
    char x = 'c';
 
    cout << countSubStr(str, n, x);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
 
// Function to return the count of
// required sub-strings
static int countSubStr(String str, int n, char x)
{
    int res = 0, count = 0;
    for (int i = 0; i < n; i++)
    {
        if (str.charAt(i) == x)
        {
 
            // Number of sub-strings from position
            // of current x to the end of str
            res += ((count + 1) * (n - i));
 
            // To store the number of characters
            // before x
            count = 0;
        }
        else
            count++;
    }
 
    return res;
}
 
// Driver code
public static void main(String[] args)
{
    String str = "abcabc";
    int n = str.length();
    char x = 'c';
 
    System.out.println(countSubStr(str, n, x));
}
}
 
// This code has been contributed by 29AjayKumar

# Python implementation of the approach
  
# Function to return the count of
# required sub-strings
def countSubStr(str, n, x):
    res = 0; count = 0;
    for i in range(n):
        if (str[i] == x):
  
            # Number of sub-strings from position
            # of current x to the end of str
            res += ((count + 1) * (n - i));
  
            # To store the number of characters
            # before x
            count = 0;
        else:
            count+=1;
  
    return res;
 
# Driver code
str = "abcabc";
n = len(str);
x = 'c';
  
print(countSubStr(str, n, x));
 
# This code contributed by PrinciRaj1992

// C# implementation of the approach
using System;
 
class GFG
{
 
// Function to return the count of
// required sub-strings
static int countSubStr(String str, int n, char x)
{
    int res = 0, count = 0;
    for (int i = 0; i < n; i++)
    {
        if (str[i] == x)
        {
 
            // Number of sub-strings from position
            // of current x to the end of str
            res += ((count + 1) * (n - i));
 
            // To store the number of characters
            // before x
            count = 0;
        }
        else
            count++;
    }
 
    return res;
}
 
// Driver code
public static void Main(String[] args)
{
    String str = "abcabc";
    int n = str.Length;
    char x = 'c';
 
    Console.WriteLine(countSubStr(str, n, x));
}
}
 
/* This code contributed by PrinciRaj1992 */

<?php
// PHP implementation of the approach
 
// Function to return the count of
// required sub-strings
function countSubStr($str, $n, $x)
{
    $res = 0; $count = 0;
    for ($i = 0; $i < $n; $i++)
    {
        if ($str[$i] == $x)
        {
 
            // Number of sub-strings from position
            // of current x to the end of str
            $res += (($count + 1) * ($n - $i));
 
            // To store the number of characters
            // before x
            $count = 0;
        }
        else
            $count++;
    }
 
    return $res;
}
 
// Driver code
$str = "abcabc";
$n = strlen($str);
$x = 'c';
 
echo countSubStr($str, $n, $x);
 
// This code is contributed by Ryuga
?>

<script>
    // Javascript implementation of the approach
     
    // Function to return the count of
    // required sub-strings
    function countSubStr(str, n, x)
    {
        let res = 0, count = 0;
        for (let i = 0; i < n; i++)
        {
            if (str[i] == x)
            {
 
                // Number of sub-strings from position
                // of current x to the end of str
                res += ((count + 1) * (n - i));
 
                // To store the number of characters
                // before x
                count = 0;
            }
            else
                count++;
        }
 
        return res;
    }
     
    let str = "abcabc";
    let n = str.length;
    let x = 'c';
   
    document.write(countSubStr(str, n, x));
 
// This code is contributed by divyeshrabadiya07.
</script>

15

Complejidad de tiempo: O(N), donde N es la longitud de la string dada.

Espacio auxiliar: O(1), no se requiere espacio extra por lo que es una constante.