Recuento de substrings que no contienen todos los caracteres del conjunto {‘a’, ‘b’, ‘c’} al mismo tiempo

Dada una string str que consta solo de los caracteres ‘a’ , ‘b’ y ‘c’ , encuentre el número de substrings que no contienen los tres caracteres al mismo tiempo.
Ejemplos: 
 

Entrada: str = “abc” 
Salida: 5 
Las posibles substrings son “a”, “b”, “c”, “ab” y “bc”
Entrada: str = “babac” 
Salida: 12 
 

Enfoque: la idea es utilizar tres variables a_index , b_index y c_index para almacenar la última aparición de los caracteres a, b y c y otra variable ans para almacenar el número de substrings que no tienen al menos uno de a, b o c e inicialice su valor al número total de substrings con longitud n, es decir, n*(n+1)/2 , donde n es la longitud de la string.
Ahora simplemente atraviesa la cuerda desde el principio. En cada punto, actualice el valor de las variables al último valor siempre que lo encuentre. Dado que estamos indexando con 0, estamos actualizando el índice como i+1 en cada paso.
Además, en cada paso, debe encontrar el índice de aparición mínima del resto de los dos caracteres que no se encuentran en el paso actual.
Luego simplemente deduzca este índice de la variable ans . Esto se debe a que una vez que encontró el índice del mínimo de los caracteres restantes, está seguro de que cualquier otra substring formada al moverse hacia abajo en el índice también contendrá los tres caracteres.
Por lo tanto, el número total de todas esas substrings (las que contienen todas las letras a, b y c) formadas en este paso es el índice encontrado.
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 valid sub-strings
int CountSubstring(string str, int n)
{
 
    // Variable ans to store all the possible substrings
    // Initialize its value as total number of substrings
    // that can be formed from the given string
    int ans = (n * (n + 1)) / 2;
 
    // Stores recent index of the characters
    int a_index = 0;
    int b_index = 0;
    int c_index = 0;
 
    for (int i = 0; i < n; i++) {
 
        // If character is a update a's index
        // and the variable ans
        if (str[i] == 'a') {
            a_index = i + 1;
            ans -= min(b_index, c_index);
        }
 
        // If character is b update b's index
        // and the variable ans
        else if (str[i] == 'b') {
            b_index = i + 1;
            ans -= min(a_index, c_index);
        }
 
        // If character is c update c's index
        // and the variable ans
        else {
            c_index = i + 1;
            ans -= min(a_index, b_index);
        }
    }
 
    return ans;
}
 
// Driver code
int main()
{
    string str = "babac";
    int n = str.length();
 
    cout << CountSubstring(str, n);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
 
    // Function to return the count of valid sub-strings
    static int CountSubstring(char str[], int n)
    {
 
        // Variable ans to store all the possible substrings
        // Initialize its value as total number of substrings
        // that can be formed from the given string
        int ans = (n * (n + 1)) / 2;
 
        // Stores recent index of the characters
        int a_index = 0;
        int b_index = 0;
        int c_index = 0;
 
        for (int i = 0; i < n; i++)
        {
 
            // If character is a update a's index
            // and the variable ans
            if (str[i] == 'a')
            {
                a_index = i + 1;
                ans -= Math.min(b_index, c_index);
            }
            // If character is b update b's index
            // and the variable ans
            else if (str[i] == 'b')
            {
                b_index = i + 1;
                ans -= Math.min(a_index, c_index);
            }
            // If character is c update c's index
            // and the variable ans
            else
            {
                c_index = i + 1;
                ans -= Math.min(a_index, b_index);
            }
        }
 
        return ans;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        char str[] = "babac".toCharArray();
        int n = str.length;
 
        System.out.println(CountSubstring(str, n));
    }
}
 
// This code contributed by Rajput-Ji

# Python3 implementation of the approach
 
# Function to return the count of
# valid sub-Strings
def CountSubString(Str, n):
 
    # Variable ans to store all the possible subStrings
    # Initialize its value as total number of subStrings
    # that can be formed from the given String
    ans = (n * (n + 1)) // 2
 
    # Stores recent index of the characters
    a_index = 0
    b_index = 0
    c_index = 0
 
    for i in range(n):
 
        # If character is a update a's index
        # and the variable ans
        if (Str[i] == 'a'):
            a_index = i + 1
            ans -= min(b_index, c_index)
 
        # If character is b update b's index
        # and the variable ans
        elif (Str[i] == 'b'):
            b_index = i + 1
            ans -= min(a_index, c_index)
         
        # If character is c update c's index
        # and the variable ans
        else:
            c_index = i + 1
            ans -= min(a_index, b_index)
 
    return ans
 
# Driver code
Str = "babac"
n = len(Str)
 
print(CountSubString(Str, n))
 
# This code is contributed by mohit kumar

// C# implementation of the approach
using System;
 
class GFG
{
 
// Function to return the count of
// valid sub-strings
static int CountSubstring(char []str, int n)
{
 
    // Variable ans to store all the possible substrings
    // Initialize its value as total number of substrings
    // that can be formed from the given string
    int ans = (n * (n + 1)) / 2;
 
    // Stores recent index of the characters
    int a_index = 0;
    int b_index = 0;
    int c_index = 0;
 
    for (int i = 0; i < n; i++)
    {
 
        // If character is a update a's index
        // and the variable ans
        if (str[i] == 'a')
        {
            a_index = i + 1;
            ans -= Math.Min(b_index, c_index);
        }
        // If character is b update b's index
        // and the variable ans
        else if (str[i] == 'b')
        {
            b_index = i + 1;
            ans -= Math.Min(a_index, c_index);
        }
        // If character is c update c's index
        // and the variable ans
        else
        {
            c_index = i + 1;
            ans -= Math.Min(a_index, b_index);
        }
    }
 
    return ans;
}
 
// Driver code
public static void Main()
{
    char []str = "babac".ToCharArray();
    int n = str.Length;
 
    Console.WriteLine(CountSubstring(str, n));
}
}
 
// This code contributed
// by Akanksha Rai

<?php
    // PHP implementation of the approach
    // Function to return the count of valid sub-strings
    function CountSubstring($str,$n)
     
    {
 
        // Variable ans to store all the possible substrings
        // Initialize its value as total number of substrings
        // that can be formed from the given string
        $ans = ($n * ($n + 1)) / 2;
 
        // Stores recent index of the characters
        $a_index = 0;
        $b_index = 0;
        $c_index = 0;
 
        for ($i = 0; $i < $n; $i++)
    {
 
 
            // If character is a update a's index
            // and the variable ans
            if ($str[$i] == 'a')
            {
                $a_index = $i + 1;
                $ans -= min($b_index, $c_index);
            }
            // If character is b update b's index
            // and the variable ans
            else if ($str[$i] == 'b')
            {
                $b_index = $i + 1;
                $ans -= min($a_index, $c_index);
            }
            // If character is c update c's index
            // and the variable ans
            else
            {
                $c_index = $i + 1;
                $ans -= min($a_index, $b_index);
            }
        }
 
        return $ans;
    }
 
    // Driver code
    {
        $str = str_split("babac");
        $n = sizeof($str);
 
        echo(CountSubstring($str, $n));
    }
 
 
// This code contributed by Code_Mech.

<script>
      // JavaScript implementation of the approach
      // Function to return the count of
      // valid sub-strings
      function CountSubstring(str, n) {
        // Variable ans to store all the possible substrings
        // Initialize its value as total number of substrings
        // that can be formed from the given string
        var ans = parseInt((n * (n + 1)) / 2);
 
        // Stores recent index of the characters
        var a_index = 0;
        var b_index = 0;
        var c_index = 0;
 
        for (var i = 0; i < n; i++) {
          // If character is a update a's index
          // and the variable ans
          if (str[i] === "a") {
            a_index = i + 1;
            ans -= Math.min(b_index, c_index);
          }
          // If character is b update b's index
          // and the variable ans
          else if (str[i] === "b") {
            b_index = i + 1;
            ans -= Math.min(a_index, c_index);
          }
          // If character is c update c's index
          // and the variable ans
          else {
            c_index = i + 1;
            ans -= Math.min(a_index, b_index);
          }
        }
 
        return ans;
      }
 
      // Driver code
      var str = "babac".split("");
      var n = str.length;
 
      document.write(CountSubstring(str, n));
    </script>

12

Complejidad temporal : O(N).
Espacio Auxiliar: O(1)