Contar substrings formadas por un solo carácter distinto

Dada una string S de longitud N , la tarea es contar el número de substrings formadas por un solo carácter distinto.
Nota: Para las apariciones repetitivas de la misma substring, cuente todas las repeticiones.

Ejemplos:

Entrada: str = “ geeksforgeeks”
Salida: 15
Explicación:  Todas las substrings formadas por un único carácter distinto son {“g”, “e”, “ee”, “e”, “k”, “s”, “f” , “o”, “r”, “g”, “e”, “ee”, “e”, “k”, “s”}.

Entrada: str = «abaanndscx»
Salida: 12

Enfoque ingenuo: el enfoque más simple para resolver este problema es generar todas las substrings a partir de la string dada y contar el número de substrings que constan de un solo carácter distinto.
Complejidad de Tiempo: O(N ³ )
Espacio Auxiliar: O(1)

Enfoque efectivo: siga los pasos a continuación para optimizar el enfoque anterior:

• Inicialice una variable, digamos ans , para almacenar el recuento de dichas substrings.
• Itere sobre los caracteres de la string y verifique si el carácter anterior, digamos pre , es el mismo que el carácter actual o no.
• Si bien se encuentra que los caracteres anterior y actual son iguales, incremente los subs y agréguelos a la respuesta.
• Si se descubre que los caracteres anterior y actual son diferentes, reinicie subs a 1 .

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

#include <iostream>
using namespace std;
 
  // Function to count the number
  // of substrings made up of a
  // single distinct character
  void countSubstrings(string s)
  {
     
    // Stores the required count
    int ans = 0;
 
    // Stores the count of substrings
    // possible by using current character
    int subs = 1;
 
    // Stores the previous character
    char pre = '0';
 
    // Traverse the string
    for (auto& i : s)
    {
       
      // If current character is same
      // as the previous character
      if(pre == i)
      {
         
        // Increase count of substrings
        // possible with current character
        subs += 1;
      }
      else
      {
         
        // Reset count  of substrings
        // possible with current character
        subs = 1;
      }
 
      // Update count of substrings
      ans += subs;
 
      // Update previous character
      pre = i;
    }
    cout << ans <<endl;
  }
 
// Driver code
int main()
{
     
    string s = "geeksforgeeks";
    countSubstrings(s);
         
    return 0;
}
 
// This code is contributed by splevel62.

// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG
{
 
  // Function to count the number
  // of substrings made up of a
  // single distinct character
  static void countSubstrings(String s)
  {
     
    // Stores the required count
    int ans = 0;
 
    // Stores the count of substrings
    // possible by using current character
    int subs = 1;
 
    // Stores the previous character
    char pre = '0';
 
    // Traverse the string
    for(char i : s.toCharArray())
    {
       
      // If current character is same
      // as the previous character
      if(pre == i)
      {
         
        // Increase count of substrings
        // possible with current character
        subs += 1;
      }
      else
      {
         
        // Reset count  of substrings
        // possible with current character
        subs = 1;
      }
 
      // Update count of substrings
      ans += subs;
 
      // Update previous character
      pre = i;
    }
    System.out.println(ans);
  }
 
// Driver Code
public static void main(String[] args)
{
    String s = "geeksforgeeks";
    countSubstrings(s);
}
}
 
// This code is contributed by souravghosh0416.

# Python3 Program to
# implement the above approach
 
# Function to count the number
# of substrings made up of a
# single distinct character
 
 
def countSubstrings(s):
 
    # Stores the required count
    ans = 0
 
    # Stores the count of substrings
    # possible by using current character
    subs = 1
 
    # Stores the previous character
    pre = ''
 
    # Traverse the string
    for i in s:
 
        # If current character is same
        # as the previous character
        if pre == i:
 
            # Increase count of substrings
            # possible with current character
            subs += 1
        else:
 
            # Reset count  of substrings
            # possible with current character
            subs = 1
 
        # Update count of substrings
        ans += subs
 
        # Update previous character
        pre = i
 
    print(ans)
 
 
# Driver Code
s = 'geeksforgeeks'
countSubstrings(s)

// C# Program to
// implement the above approach
using System;
class GFG {
 
  // Function to count the number
  // of substrings made up of a
  // single distinct character
  static void countSubstrings(string s)
  {
     
    // Stores the required count
    int ans = 0;
 
    // Stores the count of substrings
    // possible by using current character
    int subs = 1;
 
    // Stores the previous character
    char pre = '0';
 
    // Traverse the string
    foreach(char i in s)
    {
       
      // If current character is same
      // as the previous character
      if(pre == i)
      {
         
        // Increase count of substrings
        // possible with current character
        subs += 1;
      }
      else
      {
         
        // Reset count  of substrings
        // possible with current character
        subs = 1;
      }
 
      // Update count of substrings
      ans += subs;
 
      // Update previous character
      pre = i;
    }
    Console.WriteLine(ans);
  }
 
  // Driver code
  static void Main() {
    string s = "geeksforgeeks";
    countSubstrings(s);
  }
}
 
// This code is contributed by divyesh072019.

<script>
    // Javascript Program to implement
    // the above approach
     
    // Function to count the number
    // of substrings made up of a
    // single distinct character
    function countSubstrings(s)
    {
 
      // Stores the required count
      let ans = 0;
 
      // Stores the count of substrings
      // possible by using current character
      let subs = 1;
 
      // Stores the previous character
      let pre = '0';
 
      // Traverse the string
      for(let i = 0; i < s.length; i++)
      {
 
        // If current character is same
        // as the previous character
        if(pre == s[i])
        {
 
          // Increase count of substrings
          // possible with current character
          subs += 1;
        }
        else
        {
 
          // Reset count  of substrings
          // possible with current character
          subs = 1;
        }
 
        // Update count of substrings
        ans += subs;
 
        // Update previous character
        pre = s[i];
      }
      document.write(ans);
    }
     
    let s = "geeksforgeeks";
    countSubstrings(s);
   
</script>

15

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