Cuente todas las substrings que tengan el carácter K

Dada una string str y un carácter K , la tarea es encontrar el recuento de todas las substrings de str que contienen el carácter K.
Ejemplos: 

Entrada: str = “geeks”, K = ‘g’ 
Salida: 5 
“g”, “ge”, “gee”, “geek” y “geeks” son las substrings válidas.
Entrada: str = «geeksforgeeks», K = ‘k’ 
Salida: 56 
 

Enfoque ingenuo Un enfoque simple será encontrar todas las substrings que tengan el carácter K de la string dada y devolver el conteo;
Enfoque eficiente: para cada índice i en la string, encuentre el primer índice j tal que i ≤ j y str[j] = K . Ahora, las substrings str[i…j], str[i…j + 1], str[i…j + 2], …, str[i…n – 1] contendrán todas el carácter K al menos una vez. El enfoque parece ser O(n ² ) al principio, pero el índice j no se volverá a calcular para cada índice i , j será un índice válido para todos los valores de i menores quej .
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 index of the
// next occurrence of character ch in str
// starting from the given index
int nextOccurrence(string str, int n,
                   int start, char ch)
{
    for (int i = start; i < n; i++) {
 
        // Return the index of the first
        // occurrence of ch
        if (str[i] == ch)
            return i;
    }
 
    // No occurrence found
    return -1;
}
 
// Function to return the count of all
// the substrings of str which contain
// the character ch at least one
int countSubStr(string str, int n, char ch)
{
 
    // To store the count of valid substrings
    int cnt = 0;
 
    // Index of the first occurrence of ch in str
    int j = nextOccurrence(str, n, 0, ch);
    for (int i = 0; i < n; i++) {
        while (j != -1 && j < i) {
            j = nextOccurrence(str, n, j + 1, ch);
        }
 
        // No occurrence of ch after index i in str
        if (j == -1)
            break;
 
        // Substrings starting at index i
        // and ending at indices j, j+1, ..., n-1
        // are all valid substring
        cnt += (n - j);
    }
 
    return cnt;
}
 
// Driver code
int main()
{
 
    string str = "geeksforgeeks";
    int n = str.length();
    char ch = 'k';
 
    cout << countSubStr(str, n, ch);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
     
    // Function to return the index of the
    // next occurrence of character ch in str
    // starting from the given index
    static int nextOccurrence(String str, int n,
                              int start, char ch)
    {
        for (int i = start; i < n; i++)
        {
     
            // Return the index of the first
            // occurrence of ch
            if (str.charAt(i) == ch)
                return i;
        }
     
        // No occurrence found
        return -1;
    }
     
    // Function to return the count of all
    // the substrings of str which contain
    // the character ch at least one
    static int countSubStr(String str,
                           int n, char ch)
    {
     
        // To store the count of valid substrings
        int cnt = 0;
     
        // Index of the first occurrence of ch in str
        int j = nextOccurrence(str, n, 0, ch);
        for (int i = 0; i < n; i++)
        {
            while (j != -1 && j < i)
            {
                j = nextOccurrence(str, n, j + 1, ch);
            }
     
            // No occurrence of ch after index i in str
            if (j == -1)
                break;
     
            // Substrings starting at index i
            // and ending at indices j, j+1, ..., n-1
            // are all valid substring
            cnt += (n - j);
        }
        return cnt;
    }
     
    // Driver code
    static public void main ( String []arg)
    {
        String str = "geeksforgeeks";
        int n = str.length();
        char ch = 'k';
         
        System.out.println(countSubStr(str, n, ch));
    }
}
 
// This code is contributed by PrinciRaj1992

# Python3 implementation of the approach
 
# Function to return the index of the
# next occurrence of character ch in strr
# starting from the given index
def nextOccurrence(strr, n, start, ch):
    for i in range(start, n):
 
        # Return the index of the first
        # occurrence of ch
        if (strr[i] == ch):
            return i
 
    # No occurrence found
    return -1
 
# Function to return the count of all
# the substrings of strr which contain
# the character ch at least one
def countSubStr(strr, n, ch):
 
    # To store the count of valid substrings
    cnt = 0
 
    # Index of the first occurrence of ch in strr
    j = nextOccurrence(strr, n, 0, ch)
 
    for i in range(n):
        while (j != -1 and j < i):
            j = nextOccurrence(strr, n, j + 1, ch)
 
        # No occurrence of ch after index i in strr
        if (j == -1):
            break
 
        # Substrings starting at index i
        # and ending at indices j, j+1, ..., n-1
        # are all valid substring
        cnt += (n - j)
 
    return cnt
 
# Driver code
strr = "geeksforgeeks"
n = len(strr)
ch = 'k'
 
print(countSubStr(strr, n, ch))
 
# This code is contributed by Mohit Kumar

// C# implementation of the approach
using System;
 
class GFG
{
     
    // Function to return the index of the
    // next occurrence of character ch in str
    // starting from the given index
    static int nextOccurrence(String str, int n,
                               int start, char ch)
    {
        for (int i = start; i < n; i++)
        {
     
            // Return the index of the first
            // occurrence of ch
            if (str[i] == ch)
                return i;
        }
     
        // No occurrence found
        return -1;
    }
     
    // Function to return the count of all
    // the substrings of str which contain
    // the character ch at least one
    static int countSubStr(String str,
                           int n, char ch)
    {
     
        // To store the count of valid substrings
        int cnt = 0;
     
        // Index of the first occurrence of ch in str
        int j = nextOccurrence(str, n, 0, ch);
        for (int i = 0; i < n; i++)
        {
            while (j != -1 && j < i)
            {
                j = nextOccurrence(str, n, j + 1, ch);
            }
     
            // No occurrence of ch after index i in str
            if (j == -1)
                break;
     
            // Substrings starting at index i
            // and ending at indices j, j+1, ..., n-1
            // are all valid substring
            cnt += (n - j);
        }
        return cnt;
    }
     
    // Driver code
    static public void Main ()
    {
        String str = "geeksforgeeks";
        int n = str.Length;
        char ch = 'k';
         
        Console.WriteLine(countSubStr(str, n, ch));
    }
}
 
// This code is contributed by AnkitRai01

<script>
      // JavaScript implementation of the approach
      // Function to return the index of the
      // next occurrence of character ch in str
      // starting from the given index
      function nextOccurrence(str, n, start, ch) {
        for (var i = start; i < n; i++) {
          // Return the index of the first
          // occurrence of ch
          if (str[i] === ch) return i;
        }
 
        // No occurrence found
        return -1;
      }
 
      // Function to return the count of all
      // the substrings of str which contain
      // the character ch at least one
      function countSubStr(str, n, ch) {
        // To store the count of valid substrings
        var cnt = 0;
 
        // Index of the first occurrence of ch in str
        var j = nextOccurrence(str, n, 0, ch);
        for (var i = 0; i < n; i++) {
          while (j !== -1 && j < i) {
            j = nextOccurrence(str, n, j + 1, ch);
          }
 
          // No occurrence of ch after index i in str
          if (j === -1) break;
 
          // Substrings starting at index i
          // and ending at indices j, j+1, ..., n-1
          // are all valid substring
          cnt += n - j;
        }
        return cnt;
      }
 
      // Driver code
      var str = "geeksforgeeks";
      var n = str.length;
      var ch = "k";
 
      document.write(countSubStr(str, n, ch));
    </script>

56