Dada una string str , la tarea es calcular el número de substrings de la string dada de modo que la frecuencia de cada elemento de la string sea casi K .
Ejemplos:
Entrada: str = “abab”, K = 1
Salida: 7
Explicación: Las substrings en las que la frecuencia de cada carácter es como máximo 1 son “a”, “b”, “a”, “b”, “ab”, “ ba” y “ab”.Entrada: str[] = “xxyyzzxx”, K = 2
Salida: 33
Enfoque: El problema dado se puede resolver utilizando la técnica de dos puntos . Iterar a través de cada carácter de la string en el rango [0, N) y mantener la frecuencia de cada carácter en un mapa desordenado . Cree una variable ptr , que almacena el índice del punto de inicio de la ventana actual. Inicialmente, el valor de ptr es 0 . Para el índice i , si la frecuencia de str[i] es menor o igual que K , agregue (i – ptr + 1) al recuento de substrings; de lo contrario, incremente el valor de ptr hasta que str[i] > K .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the count of
// substrings such that frequency
// of each character is atmost K
int cntSubstr(string str, int K)
{
// Stores the size of string
int N = str.size();
// Stores the final count
int ans = 0;
// Stores the starting index
int ptr = 0;
// Stores the frequency of
// characters of string
unordered_map<char, int> m;
// Loop to iterate through string
for (int i = 0; i < N; i++) {
// Increment the frequency of
// the current character
m[str[i]]++;
// While the frequency of char is
// greater than K, increment ptr
while (m[str[i]] > K && ptr <= i) {
m[str[ptr]]--;
ptr++;
}
// Update count
ans += (i - ptr + 1);
}
// Return Answer
return ans;
}
// Driver Code
int main()
{
string str = "abab";
int K = 1;
cout << cntSubstr(str, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the count of
// substrings such that frequency
// of each character is atmost K
static int cntSubstr(String str, int K)
{
// Stores the size of string
int N = str.length();
// Stores the final count
int ans = 0;
// Stores the starting index
int ptr = 0;
// Stores the frequency of
// characters of string
HashMap<Character,
Integer> m = new HashMap<Character,
Integer>();
// Loop to iterate through string
for(int i = 0; i < N; i++)
{
// Increment the frequency of
// the current character
int count = 0;
if (m.containsKey(str.charAt(i)))
{
count = m.get(str.charAt(i));
}
m.put(str.charAt(i), count + 1);
// While the frequency of char is
// greater than K, increment ptr
while (m.get(str.charAt(i)) > K && ptr <= i)
{
m.put(str.charAt(ptr),
m.get(str.charAt(ptr)) - 1);
ptr++;
}
// Update count
ans += (i - ptr + 1);
}
// Return Answer
return ans;
}
// Driver Code
public static void main(String[] args)
{
String str = "abab";
int K = 1;
System.out.println(cntSubstr(str, K));
}
}
// This code is contributed by ukasp
Python3
# Python Program to implement
# the above approach
# Function to find the count of
# substrings such that frequency
# of each character is atmost K
def cntSubstr(str, K):
# Stores the size of string
N = len(str)
# Stores the final count
ans = 0
# Stores the starting index
ptr = 0
# Stores the frequency of
# characters of string
m = {}
# Loop to iterate through string
for i in range(N) :
# Increment the frequency of
# the current character
if (str[i] in m):
m[str[i]] += 1
else:
m[str[i]] = 1
# While the frequency of char is
# greater than K, increment ptr
while (m[str[i]] > K and ptr <= i):
m[str[ptr]] -= 1
ptr += 1
# Update count
ans += (i - ptr + 1)
# Return Answer
return ans
# Driver Code
str = "abab"
K = 1
print(cntSubstr(str, K))
# This code is contributed by Saurabh Jaiswal
C#
// C# program for the above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG
{
// Function to find the count of
// substrings such that frequency
// of each character is atmost K
static int cntSubstr(string str, int K)
{
// Stores the size of string
int N = str.Length;
// Stores the final count
int ans = 0;
// Stores the starting index
int ptr = 0;
// Stores the frequency of
// characters of string
Dictionary<char, int> m =
new Dictionary<char, int>();
// Loop to iterate through string
for (int i = 0; i < N; i++) {
// Increment the frequency of
// the current character
int count = 0;
if (m.ContainsKey(str[i])) {
count = m[str[i]];
}
m[str[i]] = count + 1;
// While the frequency of char is
// greater than K, increment ptr
while (m[str[i]] > K && ptr <= i) {
m[str[ptr]]--;
ptr++;
}
// Update count
ans += (i - ptr + 1);
}
// Return Answer
return ans;
}
// Driver Code
public static void Main()
{
string str = "abab";
int K = 1;
Console.Write(cntSubstr(str, K));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find the count of
// substrings such that frequency
// of each character is atmost K
function cntSubstr(str, K) {
// Stores the size of string
let N = str.length;
// Stores the final count
let ans = 0;
// Stores the starting index
let ptr = 0;
// Stores the frequency of
// characters of string
let m = new Map();
// Loop to iterate through string
for (let i = 0; i < N; i++) {
// Increment the frequency of
// the current character
if (m.has(str.charAt(i)))
m.set(str[i], m.get(str[i]) + 1);
else
m.set(str[i], 1);
// While the frequency of char is
// greater than K, increment ptr
while (m.get(str[i]) > K && ptr <= i) {
m.set(str[ptr], m.get(str[ptr]) - 1);
ptr++;
}
// Update count
ans += (i - ptr + 1);
}
// Return Answer
return ans;
}
// Driver Code
let str = "abab";
let K = 1;
document.write(cntSubstr(str, K));
// This code is contributed by Potta Lokesh
</script>
Producción
7
Complejidad temporal: O(N)
Espacio auxiliar: O(N)