Dada una string S de tamaño N que consta solo de caracteres a , b y c , la tarea es encontrar el número de substrings de la string S tal que la frecuencia del carácter a sea mayor que la frecuencia del carácter c .
Ejemplos:
Entrada: S = “abcc”
Salida: 2
Explicación:
A continuación se muestran todas las posibles substrings de S(= “abcc”) que tienen la frecuencia del carácter mayor que el carácter c:
- “a”: La frecuencia de a y c es 1 y 0 respectivamente.
- “ab”: La frecuencia de a y c es 1 y 0 respectivamente.
Por lo tanto, el recuento de dichas substrings es 2.
Entrada: S = “ abcabcabcaaaaabbbccccc”
Salida: 148
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todas las substrings posibles de la string S dada y contar esas substrings que tienen un recuento de caracteres ‘a’ mayor que el recuento de caracteres ‘c’ . Después de verificar todas las substrings, imprima el valor del conteo total como resultado.
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 number of
// substrings having the frequency of
// 'a' greater than frequency of 'c'
void countSubstrings(string& s)
{
// Stores the size of the string
int n = s.length();
// Stores the resultant
// count of substrings
int ans = 0;
// Traverse the given string
for (int i = 0; i < n; i++) {
// Store the difference between
// frequency of 'a' and 'c'
int cnt = 0;
// Traverse all substrings
// beginning at index i
for (int j = i; j < n; j++) {
if (s[j] == 'a')
cnt++;
else if (s[j] == 'c')
cnt--;
// If the frequency of 'a'
// is greater than 'c'
if (cnt > 0) {
ans++;
}
}
}
// Print the answer
cout << ans;
}
// Drive Code
int main()
{
string S = "abccaab";
countSubstrings(S);
return 0;
}
Java
// Java program for the above approach
public class GFG
{
// Function to find the number of
// substrings having the frequency of
// 'a' greater than frequency of 'c'
public static void countSubstrings(String s)
{
// Stores the size of the string
int n = s.length();
// Stores the resultant
// count of substrings
int ans = 0;
// Traverse the given string
for (int i = 0; i < n; i++) {
// Store the difference between
// frequency of 'a' and 'c'
int cnt = 0;
// Traverse all substrings
// beginning at index i
for (int j = i; j < n; j++) {
if (s.charAt(j) == 'a')
cnt++;
else if (s.charAt(j) == 'c')
cnt--;
// If the frequency of 'a'
// is greater than 'c'
if (cnt > 0) {
ans++;
}
}
}
// Print the answer
System.out.println(ans);
}
// Drive Code
public static void main(String args[])
{
String S = "abccaab";
countSubstrings(S);
}
}
// This code is contributed by SoumikMondal
Python3
# python program for the above approach # Function to find the number of # substrings having the frequency of # 'a' greater than frequency of 'c' def countSubstrings(s): # Stores the size of the string n = len(s) # Stores the resultant # count of substrings ans = 0 # Traverse the given string for i in range(n): # Store the difference between # frequency of 'a' and 'c' cnt = 0 # Traverse all substrings # beginning at index i for j in range(i, n): if (s[j] == 'a'): cnt += 1 elif (s[j] == 'c'): cnt -= 1 # If the frequency of 'a' # is greater than 'c' if (cnt > 0): ans+=1 # Print the answer print (ans) # Drive Code if __name__ == '__main__': S = "abccaab" countSubstrings(S) # This code is contributed by mohit kumar 29.
Javascript
<script>
// Javascript program for the above approach
// Function to find the number of
// substrings having the frequency of
// 'a' greater than frequency of 'c'
function countSubstrings(s)
{
// Stores the size of the string
var n = s.length;
// Stores the resultant
// count of substrings
var ans = 0;
var i,j;
// Traverse the given string
for (i = 0; i < n; i++) {
// Store the difference between
// frequency of 'a' and 'c'
var cnt = 0;
// Traverse all substrings
// beginning at index i
for (j = i; j < n; j++) {
if (s[j] == 'a')
cnt++;
else if (s[j] == 'c')
cnt--;
// If the frequency of 'a'
// is greater than 'c'
if (cnt > 0) {
ans++;
}
}
}
// Print the answer
document.write(ans);
}
// Drive Code
var S = "abccaab";
countSubstrings(S);
</script>
C#
// C# program for the above approach
using System;
public class GFG {
// Function to find the number of
// substrings having the frequency of
// 'a' greater than frequency of 'c'
public static void countSubstrings(string s)
{
// Stores the size of the string
int n = s.Length;
// Stores the resultant
// count of substrings
int ans = 0;
// Traverse the given string
for (int i = 0; i < n; i++) {
// Store the difference between
// frequency of 'a' and 'c'
int cnt = 0;
// Traverse all substrings
// beginning at index i
for (int j = i; j < n; j++) {
if (s[j] == 'a')
cnt++;
else if (s[j] == 'c')
cnt--;
// If the frequency of 'a'
// is greater than 'c'
if (cnt > 0) {
ans++;
}
}
}
// Print the answer
Console.WriteLine(ans);
}
// Drive Code
public static void Main(string[] args)
{
string S = "abccaab";
countSubstrings(S);
}
}
// This code is contributed by ukasp.
Producción:
11
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar utilizando el árbol de segmentos . La idea es almacenar la diferencia de frecuencia de los caracteres ‘a’ y ‘c’ para todos los prefijos de la string S en el Node del árbol de segmentos. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos contar hasta 0 , para almacenar la diferencia entre la frecuencia de los caracteres ‘a’ y ‘c’ .
- Inicialice una variable, digamos ans a 0 , para almacenar el recuento de substrings que tienen la frecuencia del carácter ‘a’ mayor que ‘c’ .
- Inicialice el árbol de segmentos con todos los 0 , que se actualizarán al atravesar la string.
- Dado que la diferencia entre la frecuencia de los caracteres ‘a’ y ‘c’ también puede ser negativa, todas las operaciones de actualización en el árbol de segmentos se realizarán después de agregar N al índice que se actualizará para evitar índices negativos.
- Actualice el valor del índice (0 + N) en el árbol de segmentos ya que el valor inicial del conteo es 0 .
- Recorra la string dada , S sobre el rango [0, N – 1] y realice los siguientes pasos:
- Si el carácter actual es ‘a’, incremente el conteo en 1 . De lo contrario, si el carácter actual es ‘c’, disminuya la cuenta en 1.
- Realice la consulta en el árbol de segmentos para encontrar la suma de todos los valores menores que contar , ya que todas estas substrings tendrán la frecuencia de ‘a’ mayor que ‘c’ y almacenarán el valor devuelto en una variable, digamos val .
- Agregue el valor de val a la variable ans .
- Actualice el árbol de segmentos incrementando el valor en el índice (recuento + N) en 1 .
- Después de completar los pasos anteriores, imprima el valor de ans como el recuento resultante de substrings.
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 update the segment Tree
void update(int ind, vector<int>& segTree,
int n)
{
// Update the value of ind
ind += n;
// Increment the leaf node
segTree[ind]++;
for (; ind > 1; ind >>= 1) {
// Update the parent nodes
segTree[ind >> 1] = segTree[ind]
+ segTree[ind ^ 1];
}
}
// Function to get the sum of all the
// elements between low to high - 1
int query(int low, int high,
vector<int>& segTree, int n)
{
// Initialize the leaf nodes of
// the segment tree
low += n;
high += n;
int ans = 0;
while (low < high) {
// Node lies completely in the
// range of low to high
if (low % 2) {
ans += segTree[low];
low++;
}
if (high % 2) {
high--;
ans += segTree[high];
}
// Update the value of nodes
low >>= 1;
high >>= 1;
}
return ans;
}
// Function to count the number of
// substrings which have frequency of
// 'a' greater than frequency of 'c'.
void countSubstrings(string& s)
{
// Store the size of the string
int n = s.length();
// Initialize segment tree
vector<int> segTree(4 * n);
int count = 0;
// Update the initial value of
// the count
update(n, segTree, 2 * n);
// Stores the required result
int ans = 0;
// Traverse the given string
for (int i = 0; i < n; i++) {
// Increment count
if (s[i] == 'a')
count++;
// Decrement count
else if (s[i] == 'c')
count--;
// Query the segment tree to
// find the sum of all values
// less than count
int val = query(0, n + count,
segTree, 2 * n);
ans += val;
// Update the current value of
// count in the segment tree
update(n + count, segTree, 2 * n);
}
// Print the answer
cout << ans;
}
// Driver Code
int main()
{
string S = "abccaab";
countSubstrings(S);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
public class Main
{
static String s = "abccaab";
static int n = s.length();
static int[] segTree = new int[4*n];
// Function to update the segment Tree
static void update(int ind, int n)
{
// Update the value of ind
ind += n;
// Increment the leaf node
segTree[ind]++;
for (; ind > 1; ind >>= 1) {
// Update the parent nodes
segTree[ind >> 1] = segTree[ind]
+ segTree[ind ^ 1];
}
}
// Function to get the sum of all the
// elements between low to high - 1
static int query(int low, int high, int n)
{
// Initialize the leaf nodes of
// the segment tree
low += n;
high += n;
int ans = 0;
while (low < high) {
// Node lies completely in the
// range of low to high
if (low % 2 != 0) {
ans += segTree[low];
low++;
}
if (high % 2 != 0) {
high--;
ans += segTree[high];
}
// Update the value of nodes
low >>= 1;
high >>= 1;
}
return ans;
}
// Function to count the number of
// substrings which have frequency of
// 'a' greater than frequency of 'c'.
static void countSubstrings()
{
int count = 0;
// Update the initial value of
// the count
update(n, 2 * n);
// Stores the required result
int ans = 0;
// Traverse the given string
for (int i = 0; i < n; i++) {
// Increment count
if (s.charAt(i) == 'a')
count++;
// Decrement count
else if (s.charAt(i) == 'c')
count--;
// Query the segment tree to
// find the sum of all values
// less than count
int val = query(0, n + count, 2 * n);
ans += val;
// Update the current value of
// count in the segment tree
update(n + count, 2 * n);
}
// Print the answer
System.out.print(ans);
}
// Driver code
public static void main(String[] args) {
Arrays.fill(segTree, 0);
countSubstrings();
}
}
// This code is contributed by mukesh07.
Python3
# Python3 program for the above approach s = "abccaab" n = len(s) segTree = [0]*(4*n) # Function to update the segment Tree def update(ind, n): # Update the value of ind ind += n # Increment the leaf node segTree[ind]+=1 while ind > 1: # Update the parent nodes segTree[ind >> 1] = segTree[ind] + segTree[ind ^ 1] ind >>= 1 # Function to get the sum of all the # elements between low to high - 1 def query(low, high, n): # Initialize the leaf nodes of # the segment tree low += n high += n ans = 0 while (low < high): # Node lies completely in the # range of low to high if (low % 2 != 0): ans += segTree[low] low+=1 if (high % 2 != 0): high-=1 ans += segTree[high] # Update the value of nodes low >>= 1 high >>= 1 return ans # Function to count the number of # substrings which have frequency of # 'a' greater than frequency of 'c'. def countSubstrings(): count = 0 # Update the initial value of # the count update(n, 2 * n) # Stores the required result ans = 0 # Traverse the given string for i in range(n): # Increment count if (s[i] == 'a'): count+=1 # Decrement count elif (s[i] == 'c'): count-=1 # Query the segment tree to # find the sum of all values # less than count val = query(0, n + count, 2 * n) ans += val # Update the current value of # count in the segment tree update(n + count, 2 * n) # Print the answer print(ans) countSubstrings() # This code is contributed by suresh07.
C#
// C# program for the above approach
using System;
class GFG {
static string s = "abccaab";
static int n = s.Length;
static int[] segTree = new int[4*n];
// Function to update the segment Tree
static void update(int ind, int n)
{
// Update the value of ind
ind += n;
// Increment the leaf node
segTree[ind]++;
for (; ind > 1; ind >>= 1) {
// Update the parent nodes
segTree[ind >> 1] = segTree[ind]
+ segTree[ind ^ 1];
}
}
// Function to get the sum of all the
// elements between low to high - 1
static int query(int low, int high, int n)
{
// Initialize the leaf nodes of
// the segment tree
low += n;
high += n;
int ans = 0;
while (low < high) {
// Node lies completely in the
// range of low to high
if (low % 2 != 0) {
ans += segTree[low];
low++;
}
if (high % 2 != 0) {
high--;
ans += segTree[high];
}
// Update the value of nodes
low >>= 1;
high >>= 1;
}
return ans;
}
// Function to count the number of
// substrings which have frequency of
// 'a' greater than frequency of 'c'.
static void countSubstrings()
{
int count = 0;
// Update the initial value of
// the count
update(n, 2 * n);
// Stores the required result
int ans = 0;
// Traverse the given string
for (int i = 0; i < n; i++) {
// Increment count
if (s[i] == 'a')
count++;
// Decrement count
else if (s[i] == 'c')
count--;
// Query the segment tree to
// find the sum of all values
// less than count
int val = query(0, n + count, 2 * n);
ans += val;
// Update the current value of
// count in the segment tree
update(n + count, 2 * n);
}
// Print the answer
Console.Write(ans);
}
// Driver code
static void Main() {
Array.Fill(segTree, 0);
countSubstrings();
}
}
// This code is contributed by divyesh072019.
Javascript
<script>
// Javascript program for the above approach
s = "abccaab";
n = s.length
segTree = new Array(4*n);
segTree.fill(0);
// Function to update the segment Tree
function update(ind, n)
{
// Update the value of ind
ind += n;
// Increment the leaf node
segTree[ind]++;
for (; ind > 1; ind >>= 1) {
// Update the parent nodes
segTree[ind >> 1] = segTree[ind]
+ segTree[ind ^ 1];
}
}
// Function to get the sum of all the
// elements between low to high - 1
function query(low, high, n)
{
// Initialize the leaf nodes of
// the segment tree
low += n;
high += n;
let ans = 0;
while (low < high) {
// Node lies completely in the
// range of low to high
if (low % 2) {
ans += segTree[low];
low++;
}
if (high % 2) {
high--;
ans += segTree[high];
}
// Update the value of nodes
low >>= 1;
high >>= 1;
}
return ans;
}
// Function to count the number of
// substrings which have frequency of
// 'a' greater than frequency of 'c'.
function countSubstrings()
{
let count = 0;
// Update the initial value of
// the count
update(n, 2 * n);
// Stores the required result
let ans = 0;
// Traverse the given string
for (let i = 0; i < n; i++) {
// Increment count
if (s[i] == 'a')
count++;
// Decrement count
else if (s[i] == 'c')
count--;
// Query the segment tree to
// find the sum of all values
// less than count
let val = query(0, n + count, 2 * n);
ans += val;
// Update the current value of
// count in the segment tree
update(n + count, 2 * n);
}
// Print the answer
document.write(ans);
}
countSubstrings();
// This code is contributed by decode2207.
</script>
Producción:
11
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por poulami21ghosh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA