Dada una array de strings de longitud N, se permite concatenarlas en cualquier orden. Encuentre el número máximo posible de ocurrencias de ‘AB’ en la string resultante.
Ejemplos:
Entrada: N = 4, arr={ “BCA”, “BGGGA”, “JKA”, “BALB” }
Salida: 3
Concatenarlos en el orden JKA + BGGA + BCA + BALB y se convertirá en JK AB GG AB C AB ALB y tiene 3 ocurrencias de ‘AB’.Entrada: N = 3, arr={ “ABCA”, “LIBRO”, “BANDA” }
Salida: 2
Enfoque:
Calcule el número de AB dentro de cada string de antemano. Concéntrese en el cambio del número de AB que se extienden sobre dos cuerdas cuando las cuerdas se reorganizan. Los únicos caracteres que importan en cada string son su primer y último carácter.
Las strings que pueden contribuir a la respuesta son:
- Una string que comienza con B y termina con A.
- Una string que comienza con B pero no termina con A.
- Una string que no comienza con B sino que termina con A.
Sean c1, c2 y c3 el número de strings de las categorías 1, 2 y 3, respectivamente.
- Si c1 = 0, entonces la respuesta es min(c2, c3), ya que podemos tomar ambos y concatenarlos siempre que ambos estén disponibles.
- Si c1 > 0 y c2 + c3 = 0, entonces la respuesta es c1 – 1 ya que los concatenamos en orden serial uno por uno.
- Si c1 > 0 y c2 + c3 > 0 y toma min(c2, c3) = p, primero concatene la string de categoría 1 una por una y el c1 – 1 adicional ‘AB’ y luego, si las categorías 2 y 3 están disponibles, luego agregue la categoría 3 al comienzo de la string resultante actual y agregue la categoría 2 al final de la string resultante actual.
- Hay c1 – 1 + 2 = c1 + 1 ‘AB’ adicional y ahora c2 y c3 disminuyen en uno y p se convierte en p – 1 y ahora toma las
categorías 2 y 3 y súmelas siempre que ambas estén disponibles y ahora obtenemos un total de c1 + 1 + (p – 1) = c1 + p extra ‘AB’. Eso significa c1 + min(c2, c3) .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find maximum number of ABs
int maxCountAB(string s[], int n)
{
// variable A, B, AB for count strings that
// end with 'A' but not end with 'B', 'B' but
// does not end with 'A' and 'B' and ends
// with 'A' respectively.
int A = 0, B = 0, BA = 0, ans = 0;
for (int i = 0; i < n; i++) {
string S = s[i];
int L = S.size();
for (int j = 0; j < L - 1; j++) {
// 'AB' is already present in string
// before concatenate them
if (S.at(j) == 'A' &&
S.at(j + 1) == 'B') {
ans++;
}
}
// count of strings that begins
// with 'B' and ends with 'A
if (S.at(0) == 'B' && S.at(L - 1) == 'A')
BA++;
// count of strings that begins
// with 'B' but does not end with 'A'
else if (S.at(0) == 'B')
B++;
// count of strings that ends with
// 'A' but not end with 'B'
else if (S.at(L - 1) == 'A')
A++;
}
// updating the value of ans and
// add extra count of 'AB'
if (BA == 0)
ans += min(B, A);
else if (A + B == 0)
ans += BA - 1;
else
ans += BA + min(B, A);
return ans;
}
// Driver Code
int main()
{
string s[] = { "ABCA", "BOOK", "BAND" };
int n = sizeof(s) / sizeof(s[0]);
cout << maxCountAB(s, n);
return 0;
}
Java
// Java implementation of above approach
import java.util.*;
class GFG
{
// Function to find maximum number of ABs
static int maxCountAB(String s[], int n)
{
// variable A, B, AB for count strings that
// end with 'A' but not end with 'B', 'B' but
// does not end with 'A' and 'B' and ends
// with 'A' respectively.
int A = 0, B = 0, BA = 0, ans = 0;
for (int i = 0; i < n; i++)
{
String S = s[i];
int L = S.length();
for (int j = 0; j < L - 1; j++)
{
// 'AB' is already present in string
// before concatenate them
if (S.charAt(j) == 'A' &&
S.charAt(j + 1) == 'B')
{
ans++;
}
}
// count of strings that begins
// with 'B' and ends with 'A
if (S.charAt(0) == 'B' && S.charAt(L - 1) == 'A')
BA++;
// count of strings that begins
// with 'B' but does not end with 'A'
else if (S.charAt(0) == 'B')
B++;
// count of strings that ends with
// 'A' but not end with 'B'
else if (S.charAt(L - 1) == 'A')
A++;
}
// updating the value of ans and
// add extra count of 'AB'
if (BA == 0)
ans += Math.min(B, A);
else if (A + B == 0)
ans += BA - 1;
else
ans += BA + Math.min(B, A);
return ans;
}
// Driver Code
public static void main(String[] args)
{
String s[] = { "ABCA", "BOOK", "BAND" };
int n = s.length;
System.out.println(maxCountAB(s, n));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python 3 implementation of above approach # Function to find maximum number of ABs def maxCountAB(s,n): # variable A, B, AB for count strings that # end with 'A' but not end with 'B', 'B' but # does not end with 'A' and 'B' and ends # with 'A' respectively. A = 0 B = 0 BA = 0 ans = 0 for i in range(n): S = s[i] L = len(S) for j in range(L-1): # 'AB' is already present in string # before concatenate them if (S[j] == 'A' and S[j + 1] == 'B'): ans += 1 # count of strings that begins # with 'B' and ends with 'A if (S[0] == 'B' and S[L - 1] == 'A'): BA += 1 # count of strings that begins # with 'B' but does not end with 'A' elif (S[0] == 'B'): B += 1 # count of strings that ends with # 'A' but not end with 'B' elif (S[L - 1] == 'A'): A += 1 # updating the value of ans and # add extra count of 'AB' if (BA == 0): ans += min(B, A) elif (A + B == 0): ans += BA - 1 else: ans += BA + min(B, A) return ans # Driver Code if __name__ == '__main__': s = ["ABCA", "BOOK", "BAND"] n = len(s) print(maxCountAB(s, n)) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of above approach
using System;
class GFG
{
// Function to find maximum number of ABs
static int maxCountAB(string []s, int n)
{
// variable A, B, AB for count strings that
// end with 'A' but not end with 'B', 'B' but
// does not end with 'A' and 'B' and ends
// with 'A' respectively.
int A = 0, B = 0, BA = 0, ans = 0;
for (int i = 0; i < n; i++)
{
string S = s[i];
int L = S.Length;
for (int j = 0; j < L - 1; j++)
{
// 'AB' is already present in string
// before concatenate them
if (S[j] == 'A' &&
S[j + 1] == 'B')
{
ans++;
}
}
// count of strings that begins
// with 'B' and ends with 'A
if (S[0] == 'B' && S[L - 1] == 'A')
BA++;
// count of strings that begins
// with 'B' but does not end with 'A'
else if (S[0] == 'B')
B++;
// count of strings that ends with
// 'A' but not end with 'B'
else if (S[L - 1] == 'A')
A++;
}
// updating the value of ans and
// add extra count of 'AB'
if (BA == 0)
ans += Math.Min(B, A);
else if (A + B == 0)
ans += BA - 1;
else
ans += BA + Math.Min(B, A);
return ans;
}
// Driver Code
public static void Main()
{
string []s = { "ABCA", "BOOK", "BAND" };
int n = s.Length;
Console.WriteLine(maxCountAB(s, n));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// Javascript implementation of above approach
// Function to find maximum number of ABs
function maxCountAB(s, n)
{
// variable A, B, AB for count strings that
// end with 'A' but not end with 'B', 'B' but
// does not end with 'A' and 'B' and ends
// with 'A' respectively.
var A = 0, B = 0, BA = 0, ans = 0;
for (var i = 0; i < n; i++) {
var S = s[i];
var L = S.length;
for (var j = 0; j < L - 1; j++) {
// 'AB' is already present in string
// before concatenate them
if (S[j] == 'A' &&
S[j + 1] == 'B') {
ans++;
}
}
// count of strings that begins
// with 'B' and ends with 'A
if (S[0] == 'B' && S[L - 1] == 'A')
BA++;
// count of strings that begins
// with 'B' but does not end with 'A'
else if (S[0] == 'B')
B++;
// count of strings that ends with
// 'A' but not end with 'B'
else if (S[L - 1] == 'A')
A++;
}
// updating the value of ans and
// add extra count of 'AB'
if (BA == 0)
ans += Math.min(B, A);
else if (A + B == 0)
ans += BA - 1;
else
ans += BA + Math.min(B, A);
return ans;
}
// Driver Code
var s = ["ABCA", "BOOK", "BAND"];
var n = s.length;
document.write( maxCountAB(s, n));
</script>
Producción:
2