Dada una string S y un entero K , la tarea es encontrar el número de substrings que consta de al menos K caracteres distintos por pares que tienen la misma frecuencia.
Ejemplos:
Entrada: S = “abasa”, K = 2
Salida: 5
Explicación:
Las substrings al tener 2 caracteres distintos por pares con la misma frecuencia son {“ab”, “ba”, “as”, “sa”, “bas”}.
Entrada: S = “abhay”, K = 3
Salida: 4
Explicación:
Las substrings que tienen 3 caracteres distintos por pares con la misma frecuencia son {“abh”, “bha”, “hay”, “bhay”}.
Enfoque ingenuo: el enfoque más simple para resolver este problema es generar todas las substrings posibles de la string dada y verificar si se cumplen ambas condiciones. Si se determina que es cierto, aumente la cuenta . Finalmente, imprima el conteo .
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, siga los pasos a continuación para resolver el problema:
- Compruebe si las frecuencias de cada carácter son las mismas. Si se determina que es cierto, simplemente genere todas las substrings para comprobar si cada carácter cumple la condición de al menos N caracteres distintos por pares .
- Calcule previamente las frecuencias de los caracteres para comprobar las condiciones de cada substring.
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 substring with K
// pairwise distinct characters and
// with same frequency
int no_of_substring(string s, int N)
{
// Stores the occurrence of each
// character in the substring
int fre[26];
int str_len;
// Length of the string
str_len = (int)s.length();
int count = 0;
// Iterate over the string
for (int i = 0; i < str_len; i++) {
// Set all values at each index to zero
memset(fre, 0, sizeof(fre));
int max_index = 0;
// Stores the count of
// unique characters
int dist = 0;
// Moving the substring ending at j
for (int j = i; j < str_len; j++) {
// Calculate the index of
// character in frequency array
int x = s[j] - 'a';
if (fre[x] == 0)
dist++;
// Increment the frequency
fre[x]++;
// Update the maximum index
max_index = max(max_index, fre[x]);
// Check for both the conditions
if (dist >= N && ((max_index * dist)
== (j - i + 1)))
count++;
}
}
// Return the answer
return count;
}
// Driver Code
int main()
{
string s = "abhay";
int N = 3;
// Function call
cout << no_of_substring(s, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the subString with K
// pairwise distinct characters and
// with same frequency
static int no_of_subString(String s, int N)
{
// Stores the occurrence of each
// character in the subString
int fre[] = new int[26];
int str_len;
// Length of the String
str_len = (int)s.length();
int count = 0;
// Iterate over the String
for(int i = 0; i < str_len; i++)
{
// Set all values at each index to zero
Arrays.fill(fre, 0);
int max_index = 0;
// Stores the count of
// unique characters
int dist = 0;
// Moving the subString ending at j
for(int j = i; j < str_len; j++)
{
// Calculate the index of
// character in frequency array
int x = s.charAt(j) - 'a';
if (fre[x] == 0)
dist++;
// Increment the frequency
fre[x]++;
// Update the maximum index
max_index = Math.max(max_index, fre[x]);
// Check for both the conditions
if (dist >= N && ((max_index * dist) ==
(j - i + 1)))
count++;
}
}
// Return the answer
return count;
}
// Driver Code
public static void main(String[] args)
{
String s = "abhay";
int N = 3;
// Function call
System.out.print(no_of_subString(s, N));
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program to implement
# the above approach
# Function to find the substring with K
# pairwise distinct characters and
# with same frequency
def no_of_substring(s, N):
# Length of the string
str_len = len(s)
count = 0
# Iterate over the string
for i in range(str_len):
# Stores the occurrence of each
# character in the substring
# Set all values at each index to zero
fre = [0] * 26
max_index = 0
# Stores the count of
# unique characters
dist = 0
# Moving the substring ending at j
for j in range(i, str_len):
# Calculate the index of
# character in frequency array
x = ord(s[j]) - ord('a')
if (fre[x] == 0):
dist += 1
# Increment the frequency
fre[x] += 1
# Update the maximum index
max_index = max(max_index, fre[x])
# Check for both the conditions
if(dist >= N and
((max_index * dist) == (j - i + 1))):
count += 1
# Return the answer
return count
# Driver Code
s = "abhay"
N = 3
# Function call
print(no_of_substring(s, N))
# This code is contributed by Shivam Singh
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the subString with K
// pairwise distinct characters and
// with same frequency
static int no_of_subString(String s, int N)
{
// Stores the occurrence of each
// character in the subString
int []fre = new int[26];
int str_len;
// Length of the String
str_len = (int)s.Length;
int count = 0;
// Iterate over the String
for(int i = 0; i < str_len; i++)
{
// Set all values at each index to zero
fre = new int[26];
int max_index = 0;
// Stores the count of
// unique characters
int dist = 0;
// Moving the subString ending at j
for(int j = i; j < str_len; j++)
{
// Calculate the index of
// character in frequency array
int x = s[j] - 'a';
if (fre[x] == 0)
dist++;
// Increment the frequency
fre[x]++;
// Update the maximum index
max_index = Math.Max(max_index, fre[x]);
// Check for both the conditions
if (dist >= N && ((max_index * dist) ==
(j - i + 1)))
count++;
}
}
// Return the answer
return count;
}
// Driver Code
public static void Main(String[] args)
{
String s = "abhay";
int N = 3;
// Function call
Console.Write(no_of_subString(s, N));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// javascript program for the above approach
// Function to find the subString with K
// pairwise distinct characters and
// with same frequency
function no_of_subString(s , N)
{
// Stores the occurrence of each
// character in the subString
var fre = Array.from({length: 26}, (_, i) => 0);
var str_len;
// Length of the String
str_len = parseInt(s.length);
var count = 0;
// Iterate over the String
for(i = 0; i < str_len; i++)
{
// Set all values at each index to zero
fre = Array(26).fill(0);
var max_index = 0;
// Stores the count of
// unique characters
var dist = 0;
// Moving the subString ending at j
for(j = i; j < str_len; j++)
{
// Calculate the index of
// character in frequency array
var x = s.charAt(j).charCodeAt(0) - 'a'.charCodeAt(0);
if (fre[x] == 0)
dist++;
// Increment the frequency
fre[x]++;
// Update the maximum index
max_index = Math.max(max_index, fre[x]);
// Check for both the conditions
if (dist >= N && ((max_index * dist) ==
(j - i + 1)))
count++;
}
}
// Return the answer
return count;
}
// Driver Code
var s = "abhay";
var N = 3;
// Function call
document.write(no_of_subString(s, N));
// This code contributed by shikhasingrajput
</script>
Producción:
4
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por thakurabhaysingh445 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA