Dada la string str de tamaño N que consiste solo en 0 , 1 y 2 , la tarea es encontrar la cantidad de substrings que consisten en los caracteres 0 , 1 y 2 al menos una vez.
Ejemplos:
Entrada: str = “0122”
Salida: 2
Explicación:
Existen 2 substrings tales que las substrings tienen los caracteres 0, 1, 2 al menos una vez es “012” y “0122”. Por lo tanto, el recuento de substrings es 2.Entrada: S = “00021”
Salida: 3
Enfoque: el problema dado se puede resolver utilizando la técnica de la ventana deslizante , la idea es hacer el arreglo de frecuencias del tamaño 3 que contiene la ocurrencia de 0 , 1 y 2 . Recorra la string dada y actualice la array de frecuencias en consecuencia, si los 3 índices de la array son mayores que cero, cuente el mínimo de ellos e increméntelo en la variable count . Siga los pasos a continuación para resolver el problema:
- Inicialice una array freq[] de tamaño 3 para almacenar la frecuencia de todos los elementos de la array.
- Inicialice la variable count como 0 para almacenar la respuesta e i como 0 para mantener el puntero izquierdo.
- Itere sobre el rango [0, N) usando la variable j y realice las siguientes tareas:
- Aumente la frecuencia del carácter actual str[ I ] en la array freq[] en 1.
- Atraviese un bucle while hasta que freq[0], freq[1] y freq[2] sean mayores que 0, disminuya la frecuencia del carácter en la i-ésima posición en 1 y aumente el valor de i en 1.
- Agregue el valor de i a la variable conteo.
- Después de realizar los pasos anteriores, imprima el valor de conteo como respuesta.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for above approach
#include <iostream>
#include <string>
using namespace std;
// Function to count the number of
// substrings consists of 0, 1, and 2
int countSubstrings(string& str)
{
// Initialize frequency array
// of size 3
int freq[3] = { 0 };
// Stores the resultant count
int count = 0;
int i = 0;
// Traversing string str
for (int j = 0; j < str.length(); j++) {
// Update frequency array
freq[str[j] - '0']++;
// If all the characters are
// present counting number of
// substrings possible
while (freq[0] > 0 && freq[1] > 0 && freq[2] > 0) {
freq[str[i++] - '0']--;
}
// Update number of substrings
count += i;
}
// Return the number of substrings
return count;
}
// Driver Code
int main()
{
string str = "00021";
int count = countSubstrings(str);
cout << count;
return 0;
}
// This code is contributed by Kdheeraj.
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to count the number of
// substrings consists of 0, 1, and 2
public static int countSubstrings(String str)
{
// Initialize frequency array
// of size 3
int[] freq = new int[3];
// Stores the resultant count
int count = 0;
int i = 0;
// Traversing string str
for (int j = 0;
j < str.length(); j++) {
// Update frequency array
freq[str.charAt(j) - '0']++;
// If all the characters are
// present counting number of
// substrings possible
while (freq[0] > 0 && freq[1] > 0
&& freq[2] > 0) {
freq[str.charAt(i++) - '0']--;
}
// Update number of substrings
count += i;
}
// Return the number of substrings
return count;
}
// Driver Code
public static void main(String[] args)
{
String str = "00021";
System.out.println(
countSubstrings(str));
}
}
Python3
# Python program for above approach
# Function to count the number of
# substrings consists of 0, 1, and 2
def countSubstrings(str):
# Initialize frequency array
# of size 3
freq = [ 0 ]*3
# Stores the resultant count
count = 0
i = 0
# Traversing string str
for j in range ( 0 ,len(str)):
# Update frequency array
freq[ord(str[j]) - ord('0')] += 1
# If all the characters are
# present counting number of
# substrings possible
while (freq[0] > 0 and freq[1] > 0 and freq[2] > 0):
i += 1
freq[ord(str[i]) - ord('0')] -= 1
# Update number of substrings
count += i
# Return the number of substrings
return count
# Driver Code
str = "00021"
count = countSubstrings(str)
print(count)
# This code is contributed by shivanisinghss2110
C#
// C# program for the above approach
using System;
class GFG {
// Function to count the number of
// substrings consists of 0, 1, and 2
public static int countSubstrings(string str)
{
// Initialize frequency array
// of size 3
int[] freq = new int[3];
// Stores the resultant count
int count = 0;
int i = 0;
// Traversing string str
for (int j = 0;
j < str.Length; j++) {
// Update frequency array
freq[str[j] - '0']++;
// If all the characters are
// present counting number of
// substrings possible
while (freq[0] > 0 && freq[1] > 0
&& freq[2] > 0) {
freq[str[i++] - '0']--;
}
// Update number of substrings
count += i;
}
// Return the number of substrings
return count;
}
// Driver Code
public static void Main(String[] args)
{
string str = "00021";
Console.Write(countSubstrings(str));
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to count the number of
// substrings consists of 0, 1, and 2
function countSubstrings(str) {
// Initialize frequency array
// of size 3
let freq = new Array(3).fill(0)
// Stores the resultant count
let count = 0;
let i = 0;
// Traversing string str
for (let j = 0; j < str.length; j++) {
// Update frequency array
freq[str.charCodeAt(j) - '0'.charCodeAt(0)]++;
// If all the characters are
// present counting number of
// substrings possible
while (freq[0] > 0 && freq[1] > 0 && freq[2] > 0) {
freq[str.charCodeAt(i++) - '0'.charCodeAt(0)]--;
}
// Update number of substrings
count += i;
}
// Return the number of substrings
return count;
}
// Driver Code
let str = "00021";
let count = countSubstrings(str);
document.write(count);
// This code is contributed by Potta Lokesh
</script>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)