Dada una string S y un carácter C, la tarea es contar el número de substrings de S que contienen solo el carácter C.
Ejemplos:
Entrada : S = “0110111”, C = ‘1’
Salida: 9
Explicación:
Las substrings que contienen solo ‘1’ son:
“1” — 5 veces
“11” — 3 veces
“111” — 1 vez
Por lo tanto, el conteo es 9.Entrada: S = «geeksforgeeks», C = ‘e’
Salida: 6
Enfoque ingenuo:
el enfoque más simple es generar todas las substrings posibles de la string S dada y contar las substrings que contienen solo el carácter C.
Complejidad de tiempo: O(N 3 )
Complejidad de espacio: O(1)
Enfoque eficiente:
Para optimizar el enfoque anterior , se puede aplicar el hecho de que una string de longitud N forma N*(N+1)/2 substrings. Por lo tanto, para N ocurrencias consecutivas del carácter C en la string, se generan N*(N+1)/2 substrings. Por lo tanto, iterar a través de toda la longitud de la string Sy para cada substring consecutiva del carácter C, cuente el número posible de substrings posibles a partir de ellas y súmelas al recuento total de substrings posibles.
Ilustración:
S = “0110111”, C = ‘1’
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function that finds the count
// of substrings containing only
// character C in the string S
void countSubString(string S, char C)
{
// To store total count
// of substrings
int count = 0;
// To store count of
// consecutive C's
int conCount = 0;
// Loop through the string
for (char ch : S) {
// Increase the consecutive
// count of C's
if (ch == C)
conCount++;
else {
// Add count of sub-strings
// from consecutive strings
count += (conCount
* (conCount + 1))
/ 2;
// Reset the consecutive
// count of C's
conCount = 0;
}
}
// Add count of sub-strings from
// consecutive strings
count += (conCount
* (conCount + 1))
/ 2;
// Print the count of sub-strings
// containing only C
cout << count;
}
// Driver Code
int main()
{
string S = "geeksforgeeks";
char C = 'e';
countSubString(S, C);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function that finds the count
// of substrings containing only
// character C in the string S
static void countSubString(String S, char C)
{
// To store total count
// of substrings
int count = 0;
// To store count of
// consecutive C's
int conCount = 0;
// Loop through the string
for(int i = 0; i < S.length(); i++)
{
char ch = S.charAt(i);
// Increase the consecutive
// count of C's
if (ch == C)
conCount++;
else
{
// Add count of sub-strings
// from consecutive strings
count += (conCount *
(conCount + 1)) / 2;
// Reset the consecutive
// count of C's
conCount = 0;
}
}
// Add count of sub-strings from
// consecutive strings
count += (conCount *
(conCount + 1)) / 2;
// Print the count of sub-strings
// containing only C
System.out.println(count);
}
// Driver Code
public static void main(String s[])
{
String S = "geeksforgeeks";
char C = 'e';
countSubString(S, C);
}
}
// This code is contributed by rutvik_56
Python3
# Python3 program to implement # the above approach # Function that finds the count # of substrings containing only # character C in the S def countSubString(S, C): # To store total count # of substrings count = 0 # To store count of # consecutive C's conCount = 0 # Loop through the string for ch in S: # Increase the consecutive # count of C's if (ch == C): conCount += 1 else: # Add count of sub-strings # from consecutive strings count += ((conCount * (conCount + 1)) // 2) # Reset the consecutive # count of C's conCount = 0 # Add count of sub-strings from # consecutive strings count += ((conCount * (conCount + 1)) // 2) # Print the count of sub-strings # containing only C print(count) # Driver Code if __name__ == '__main__': S = "geeksforgeeks" C = 'e' countSubString(S, C) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Function that finds the count
// of substrings containing only
// character C in the string S
static void countSubString(String S, char C)
{
// To store total count
// of substrings
int count = 0;
// To store count of
// consecutive C's
int conCount = 0;
// Loop through the string
for(int i = 0; i < S.Length; i++)
{
char ch = S[i];
// Increase the consecutive
// count of C's
if (ch == C)
conCount++;
else
{
// Add count of sub-strings
// from consecutive strings
count += (conCount *
(conCount + 1)) / 2;
// Reset the consecutive
// count of C's
conCount = 0;
}
}
// Add count of sub-strings from
// consecutive strings
count += (conCount *
(conCount + 1)) / 2;
// Print the count of sub-strings
// containing only C
Console.Write(count);
}
// Driver Code
public static void Main(String[] args)
{
String S = "geeksforgeeks";
char C = 'e';
countSubString(S, C);
}
}
// This code is contributed by grand_master
Javascript
<script>
// Javascript program for the above approach
// Function that finds the count
// of substrings containing only
// character C in the string S
function countSubString(S, C) {
// To store total count
// of substrings
var count = 0;
// To store count of
// consecutive C's
var conCount = 0;
// Loop through the string
for (var i = 0; i < S.length; i++) {
var ch = S[i];
// Increase the consecutive
// count of C's
if (ch === C) conCount++;
else {
// Add count of sub-strings
// from consecutive strings
count += (conCount * (conCount + 1)) / 2;
// Reset the consecutive
// count of C's
conCount = 0;
}
}
// Add count of sub-strings from
// consecutive strings
count += (conCount * (conCount + 1)) / 2;
// Print the count of sub-strings
// containing only C
document.write(count);
}
// Driver Code
var S = "geeksforgeeks";
var C = "e";
countSubString(S, C);
</script>
6
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por Rohit_prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA