Dada una string str y un carácter c . La tarea es encontrar el número de substrings que no constan del carácter c .
Ejemplos:
Entrada: str = “baa”, c = ‘b’
Salida: 3
Las substrings son “a”, “a” y “aa”
Entrada: str = “ababaa”, C = ‘b’
Salida: 5
Enfoque: Inicialmente tome un contador que cuente el número de caracteres continuamente sin el carácter c . Iterar en la string y aumentar el contador hasta str[i] != c . Una vez que str[i] == c , el número de substrings de la longitud contigua cnt será (cnt * (cnt + 1)) / 2 . Después del recorrido completo de la string, también agregue (cnt *(cnt + 1)) / 2 al resultado para el grupo de caracteres que aparece después de la última aparición de c .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the number
// of sub-strings that do not contain
// the given character c
int countSubstrings(string s, char c)
{
// Length of the string
int n = s.length();
int cnt = 0;
int sum = 0;
// Traverse in the string
for (int i = 0; i < n; i++) {
// If current character is different
// from the given character
if (s[i] != c)
cnt++;
else {
// Update the number of sub-strings
sum += (cnt * (cnt + 1)) / 2;
// Reset count to 0
cnt = 0;
}
}
// For the characters appearing
// after the last occurrence of c
sum += (cnt * (cnt + 1)) / 2;
return sum;
}
// Driver code
int main()
{
string s = "baa";
char c = 'b';
cout << countSubstrings(s, c);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the number
// of sub-strings that do not contain
// the given character c
static int countSubstrings(String s, char c)
{
// Length of the string
int n = s.length();
int cnt = 0;
int sum = 0;
// Traverse in the string
for (int i = 0; i < n; i++)
{
// If current character is different
// from the given character
if (s.charAt(i) != c)
cnt++;
else
{
// Update the number of sub-strings
sum += (cnt * (cnt + 1)) / 2;
// Reset count to 0
cnt = 0;
}
}
// For the characters appearing
// after the last occurrence of c
sum += (cnt * (cnt + 1)) / 2;
return sum;
}
// Driver code
public static void main(String[] args)
{
String s = "baa";
char c = 'b';
System.out.println(countSubstrings(s, c));
}
}
// This code is contributed by Code_Mech.
Python3
# Python3 implementation of the approach # Function to return the number # of sub-strings that do not contain # the given character c def countSubstrings(s, c): # Length of the string n = len(s) cnt = 0 Sum = 0 # Traverse in the string for i in range(n): # If current character is different # from the given character if (s[i] != c): cnt += 1 else: # Update the number of sub-strings Sum += (cnt * (cnt + 1)) // 2 # Reset count to 0 cnt = 0 # For the characters appearing # after the last occurrence of c Sum += (cnt * (cnt + 1)) // 2 return Sum # Driver code s = "baa" c = 'b' print(countSubstrings(s, c)) # This code is contributed # by mohit kumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the number
// of sub-strings that do not contain
// the given character c
static int countSubstrings(string s, char c)
{
// Length of the string
int n = s.Length;
int cnt = 0;
int sum = 0;
// Traverse in the string
for (int i = 0; i < n; i++)
{
// If current character is different
// from the given character
if (s[i] != c)
cnt++;
else
{
// Update the number of sub-strings
sum += (cnt * (cnt + 1)) / 2;
// Reset count to 0
cnt = 0;
}
}
// For the characters appearing
// after the last occurrence of c
sum += (cnt * (cnt + 1)) / 2;
return sum;
}
// Driver code
public static void Main()
{
string s = "baa";
char c = 'b';
Console.Write(countSubstrings(s, c));
}
}
// This code is contributed by Akanksha Rai
PHP
<?php
// PHP implementation of the approach
// Function to return the number
// of sub-strings that do not contain
// the given character c
function countSubstrings($s, $c)
{
// Length of the string
$n = strlen($s);
$cnt = 0;
$sum = 0;
// Traverse in the string
for ($i = 0; $i < $n; $i++)
{
// If current character is different
// from the given character
if ($s[$i] != $c)
$cnt++;
else
{
// Update the number of sub-strings
$sum += floor(($cnt * ($cnt + 1)) / 2);
// Reset count to 0
$cnt = 0;
}
}
// For the characters appearing
// after the last occurrence of c
$sum += floor(($cnt * ($cnt + 1)) / 2);
return $sum;
}
// Driver code
$s = "baa";
$c = 'b';
echo countSubstrings($s, $c);
// This code is contributed by Ryuga
?>
Javascript
<script>
// javascript implementation of the approach
// Function to return the number
// of sub-strings that do not contain
// the given character c
function countSubstrings( s, c) {
// Length of the string
var n = s.length;
var cnt = 0;
var sum = 0;
// Traverse in the string
for (i = 0; i < n; i++) {
// If current character is different
// from the given character
if (s.charAt(i) != c)
cnt++;
else {
// Update the number of sub-strings
sum += (cnt * (cnt + 1)) / 2;
// Reset count to 0
cnt = 0;
}
}
// For the characters appearing
// after the last occurrence of c
sum += (cnt * (cnt + 1)) / 2;
return sum;
}
// Driver code
var s = "baa";
var c = 'b';
document.write(countSubstrings(s, c));
// This code contributed by umadevi9616
</script>
Producción:
3
Complejidad de tiempo: O(n) donde n es la longitud de la string
Espacio auxiliar: O(1)