Dada una string S que consta de solo los caracteres ‘a’ y ‘b’ , y un número entero N. La string S se suma N veces para obtener la string T. Su tarea es contar el número de prefijos donde el número de a es estrictamente mayor que el de b.
cuerda T = S + S + S + S ……. N veces.
Ejemplos:
Input : aba 2 Output : 5 Explanation : The string T is "abaaba". It has five prefixes which contain more a-s than b-s: "a", "aba", "abaa", "abaab" and "abaaba". Input : baa 3 Output : 6 Explanation : The string T is "baabaabaa". The strings "baa", "baaba", "baabaa", "baabaab", "baabaaba" and "baabaabaa" are the six valid prefixes.
Enfoque ingenuo: una forma simple de hacer este programa es generar la string T completa y luego ejecutar un bucle para verificar los prefijos válidos donde el número de a es mayor que el número de b. Si el valor de N es muy grande, este método no es eficiente y requiere mucho tiempo.
Enfoque eficiente:
tenga en cuenta que la string es repetitiva. Por lo tanto, no tenemos que verificar la string completa T.
Operar en la string S. Let,
count = Número de prefijos en la string S
A = Frecuencia del carácter ‘a’ en la string S
B = Frecuencia del carácter ‘b’ en la string S
CASO 1: cuenta == 0
Si el número de prefijos válidos es cero. Entonces, incluso si generamos la String T completa, el número de prefijos válidos seguirá siendo cero.
CASO 2: cuenta >0
Este caso tiene tres subcasos:
a. A == B
En este caso, no hay efecto de concatenaciones anteriores de S en la concatenación entrante/nueva de S. En otras palabras, cuando A != B, entonces hay algún cambio en el valor de (AB) después de cada adición de S a T, lo que afecta la contribución de cualquier concatenación futura de S hacia el conteo. Significa que dado que A == B, entonces el número de b en T no aumentará al mismo ritmo que el número de a en cada adición, lo que afectará la contribución de la próxima adición a la respuesta final. Este no es el caso cuando A == B . Por lo tanto, cada adición de S contribuirá a contar para la respuesta final. Hay N sumas de S y ya encontramos el conteo por bucle simple anteriormente. Por lo tanto, para este caso, Respuesta = cuenta * N.
b. A <B
En este caso, debido a que A < B, cada nueva adición de S a T disminuirá AB. En otras palabras, el número de b en T aumentará más rápidamente que el número de a, lo que reducirá la contribución de cada futura adición de S hacia la respuesta final. Vemos que, después de cada adición, la contribución de la próxima adición debe reducirse al menos en 1. Así, gradualmente, el recuento por nueva string convergerá a cero. Así que tenemos que comprobar hasta que eso suceda.
Por ejemplo, Say count de la string S converge a cero después de 1000 sumas. Si N = 99999, solo tenemos que verificar hasta 1000 e ignorar el resto de los casos. Si N = 5, tenemos que calcular hasta 5 sumas.
C. A > B
Claramente, cada nueva adición de S a T aumentará AB. Por lo tanto, el número de a en T aumentará más rápidamente que el número de b, lo que aumentará la contribución de cada adición futura de S hacia la respuesta final. La máxima contribución posible de una adición a nuestra respuesta puede ser |S|, es decir, la longitud de la string S. Por lo tanto, el recuento por string se saturará hasta la longitud de la string después de algunas adiciones. Tenemos que comprobar hasta que eso suceda.
Por ejemplo: digamos que el recuento de la string S se satura hasta la longitud de S después de X adiciones. Entonces, tenemos que calcular contar hasta X, luego agregar el residuo que es igual a (NX)*longitud de S (iff N>X)
si N<X entonces tenemos que calcular hasta N adiciones.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP code to count the prefixes
// with more a than b
#include <bits/stdc++.h>
using namespace std;
// Function to count prefixes
int prefix(string k, int n)
{
int a = 0, b = 0, count = 0;
int i = 0;
int len = k.size();
// calculating for string S
for (i = 0; i < len; i++) {
if (k[i] == 'a')
a++;
if (k[i] == 'b')
b++;
if (a > b) {
count++;
}
}
// count==0 or when N==1
if (count == 0 || n == 1) {
cout << count << endl;
return 0;
}
// when all characters are a or a-b==0
if (count == len || a - b == 0) {
cout << count * n << endl;
return 0;
}
int n2 = n - 1, count2 = 0;
// checking for saturation of
// string after repetitive addition
while (n2 != 0) {
for (i = 0; i < len; i++) {
if (k[i] == 'a')
a++;
if (k[i] == 'b')
b++;
if (a > b) {
count2++;
}
}
count += count2;
n2--;
if (count2 == 0)
break;
if (count2 == len) {
count += (n2 * count2);
break;
}
count2 = 0;
}
return count;
}
// Driver function
int main()
{
string S = "aba";
int N = 2;
cout << prefix(S, N) << endl;
S = "baa";
N = 3;
cout << prefix(S, N) << endl;
return 0;
}
Java
// Java code to count the
// prefixes with more a than b
import java.io.*;
class GFG
{
// Function to
// count prefixes
static int prefix(String k, int n)
{
int a = 0, b = 0,
count = 0;
int i = 0;
int len = k.length();
// calculating for string S
for (i = 0; i < len; i++)
{
if (k.charAt(i) == 'a')
a++;
if (k.charAt(i) == 'b')
b++;
if (a > b)
{
count++;
}
}
// count==0 or when N==1
if (count == 0 || n == 1)
{
System.out.println(count);
return 0;
}
// when all characters
// are a or a-b==0
if (count == len || a - b == 0)
{
System.out.println(count * n);
return 0;
}
int n2 = n - 1, count2 = 0;
// checking for saturation
// of string after repetitive
// addition
while (n2 != 0)
{
for (i = 0; i < len; i++)
{
if (k.charAt(i) == 'a')
a++;
if (k.charAt(i) == 'b')
b++;
if (a > b)
{
count2++;
}
}
count += count2;
n2--;
if (count2 == 0)
break;
if (count2 == len)
{
count += (n2 * count2);
break;
}
count2 = 0;
}
return count;
}
// Driver Code
public static void main (String[] args)
{
String S = "aba";
int N = 2;
System.out.println(prefix(S, N));
S = "baa";
N = 3;
System.out.println(prefix(S, N)) ;
}
}
// This code is contributed
// by anuj_67.
Python3
# Python3 code to count the prefixes # with more a than b # Function to count prefixes def prefix(k, n): a = 0 b = 0 count = 0 i = 0 Len = len(k) # calculating for string S for i in range(Len): if (k[i] == "a"): a += 1 if (k[i] == "b"): b += 1 if (a > b) : count += 1 # count==0 or when N==1 if (count == 0 or n == 1): print(count) return 0 # when all characters are a or a-b==0 if (count == Len or a - b == 0) : print(count * n) return 0 n2 = n - 1 count2 = 0 # checking for saturation of # string after repetitive addition while (n2 != 0): for i in range(Len): if (k[i] == "a"): a += 1 if (k[i] == "b"): b += 1 if (a > b): count2 += 1 count += count2 n2 -= 1 if (count2 == 0): break if (count2 == Len): count += (n2 * count2) break count2 = 0 return count # Driver Code S = "aba" N = 2 print(prefix(S, N)) S = "baa" N = 3 print(prefix(S, N)) # This code is contributed by # Mohit kumar 29
C#
// C# code to count the
// prefixes with more
// a than b
using System;
class GFG
{
// Function to
// count prefixes
static int prefix(String k, int n)
{
int a = 0, b = 0,
count = 0;
int i = 0;
int len = k.Length;
// calculating for string S
for (i = 0; i < len; i++)
{
if (k[i] == 'a')
a++;
if (k[i] == 'b')
b++;
if (a > b)
{
count++;
}
}
// count==0 or when N==1
if (count == 0 || n == 1)
{
Console.WriteLine(count);
return 0;
}
// when all characters
// are a or a-b==0
if (count == len ||
a - b == 0)
{
Console.WriteLine(count * n);
return 0;
}
int n2 = n - 1, count2 = 0;
// checking for saturation
// of string after repetitive
// addition
while (n2 != 0)
{
for (i = 0; i < len; i++)
{
if (k[i] == 'a')
a++;
if (k[i] == 'b')
b++;
if (a > b)
{
count2++;
}
}
count += count2;
n2--;
if (count2 == 0)
break;
if (count2 == len)
{
count += (n2 * count2);
break;
}
count2 = 0;
}
return count;
}
// Driver Code
public static void Main ()
{
string S = "aba";
int N = 2;
Console.WriteLine(prefix(S, N));
S = "baa";
N = 3;
Console.WriteLine(prefix(S, N)) ;
}
}
// This code is contributed
// by anuj_67.
PHP
<?php
// PHP code to count the
// prefixes with more a than b
// Function to count prefixes
function prefix($k, $n)
{
$a = 0; $b = 0; $count = 0;
$i = 0;
$len = strlen($k);
// calculating for string S
for ($i = 0; $i < $len; $i++)
{
if ($k[$i] == 'a')
$a++;
if ($k[$i] == 'b')
$b++;
if ($a > $b)
{
$count++;
}
}
// count==0 or when N==1
if ($count == 0 || $n == 1)
{
echo($count);
return 0;
}
// when all characters
// are a or a-b==0
if ($count == $len || $a - $b == 0)
{
echo($count * $n);
return 0;
}
$n2 = $n - 1; $count2 = 0;
// checking for saturation
// of string after repetitive
// addition
while ($n2 != 0)
{
for ($i = 0; $i < $len; $i++)
{
if ($k[$i] == 'a')
$a++;
if ($k[$i] == 'b')
$b++;
if ($a > $b)
{
$count2++;
}
}
$count += $count2;
$n2--;
if ($count2 == 0)
break;
if ($count2 == $len)
{
$count += ($n2 * $count2);
break;
}
$count2 = 0;
}
return $count;
}
// Driver Code
$S = "aba";
$N = 2;
echo(prefix($S,$N)."\n");
$S = "baa";
$N = 3;
echo(prefix($S, $N)."\n");
// This code is contributed
// by Mukul Singh.
Javascript
<script>
// Javascript code to count the
// prefixes with more a than b
// Function to
// count prefixes
function prefix(k,n)
{
let a = 0, b = 0,
count = 0;
let i = 0;
let len = k.length;
// calculating for string S
for (i = 0; i < len; i++)
{
if (k[i] == 'a')
a++;
if (k[i] == 'b')
b++;
if (a > b)
{
count++;
}
}
// count==0 or when N==1
if (count == 0 || n == 1)
{
document.write(count+"<br>");
return 0;
}
// when all characters
// are a or a-b==0
if (count == len || a - b == 0)
{
document.write((count * n)+"<br>");
return 0;
}
let n2 = n - 1, count2 = 0;
// checking for saturation
// of string after repetitive
// addition
while (n2 != 0)
{
for (i = 0; i < len; i++)
{
if (k[i] == 'a')
a++;
if (k[i] == 'b')
b++;
if (a > b)
{
count2++;
}
}
count += count2;
n2--;
if (count2 == 0)
break;
if (count2 == len)
{
count += (n2 * count2);
break;
}
count2 = 0;
}
return count;
}
// Driver Code
let S = "aba";
let N = 2;
document.write(prefix(S, N)+"<br>");
S = "baa";
N = 3;
document.write(prefix(S, N)+"<br>") ;
// This code is contributed by patel2127
</script>
5 6
Publicación traducida automáticamente
Artículo escrito por agnivakolay y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA