Dadas dos arrays A[] y B[] que consisten en N y M strings respectivamente. Se dice que una string S1 es más pequeña que la string S2 si la frecuencia del carácter más pequeño de S1 es menor que la frecuencia del carácter más pequeño de S2 . La tarea es contar el número de strings en A[] que son más pequeñas que B[i] para cada i .
Ejemplos:
Entrada: A[] = {“aaa”, “aa”, “bdc”}, B[] = {“cccch”, “cccd”}
Salida: 3 2
“cccch” tiene la frecuencia del carácter más pequeño como 4, y todas las strings
en A[] tienen frecuencias de los caracteres más pequeños menores que 4.
“cccd” tiene la frecuencia del carácter más pequeño como 3 y solo “aa” y “bdc”
tienen frecuencias del carácter más pequeño menos de 3.Entrada: A[] = {“abca”, “jji”}, B[] = {“jhgkki”, “aaaa”, “geeks”}
Salida: 0 2 1
Un enfoque ingenuo es tomar cada string en B[] y luego contar el número de strings en A[] que satisfarán la condición.
Un enfoque eficiente es resolverlo utilizando la búsqueda binaria y algunos cálculos previos, como se menciona a continuación:
- Inicialmente cuente la frecuencia del carácter más pequeño de cada string y guárdela en el vector / array .
- Ordene el vector/array en orden ascendente.
- Ahora, para cada string en B[i] , encuentre la frecuencia del carácter más pequeño.
- Usando la función lower_bound en C++, o haciendo una búsqueda binaria en el vector/array, encuentre el conteo de números que tiene una frecuencia menor que la frecuencia del carácter más pequeño para cada B[i] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define MAX 26
// Function to count the number of smaller
// strings in A[] for every string in B[]
vector<int> findCount(string a[], string b[], int n, int m)
{
// Count the frequency of all characters
int freq[MAX] = { 0 };
vector<int> smallestFreq;
// Iterate for all possible strings in A[]
for (int i = 0; i < n; i++) {
string s = a[i];
memset(freq, 0, sizeof freq);
// Increase the frequency of every character
for (int j = 0; j < s.size(); j++) {
freq[s[j] - 'a']++;
}
// Check for the smallest character's frequency
for (int j = 0; j < MAX; j++) {
// Get the smallest character frequency
if (freq[j]) {
// Insert it in the vector
smallestFreq.push_back(freq[j]);
break;
}
}
}
// Sort the count of all the frequency of the smallest
// character in every string
sort(smallestFreq.begin(), smallestFreq.end());
vector<int> ans;
// Iterate for every string in B[]
for (int i = 0; i < m; i++) {
string s = b[i];
// Hash set every frequency 0
memset(freq, 0, sizeof freq);
// Count the frequency of every character
for (int j = 0; j < s.size(); j++) {
freq[s[j] - 'a']++;
}
int frequency = 0;
// Find the frequency of the smallest character
for (int j = 0; j < MAX; j++) {
if (freq[j]) {
frequency = freq[j];
break;
}
}
// Count the number of strings in A[]
// which has the frequency of the smaller
// character less than the frequency of the
// smaller character of the string in B[]
int ind = lower_bound(smallestFreq.begin(),
smallestFreq.end(), frequency)
- smallestFreq.begin();
// Store the answer
ans.push_back(ind);
}
return ans;
}
// Function to print the answer
void printAnswer(string a[], string b[], int n, int m)
{
// Get the answer
vector<int> ans = findCount(a, b, n, m);
// Print the number of strings
// for every answer
for (auto it : ans) {
cout << it << " ";
}
}
// Driver code
int main()
{
string A[] = { "aaa", "aa", "bdc" };
string B[] = { "cccch", "cccd" };
int n = sizeof(A) / sizeof(A[0]);
int m = sizeof(B) / sizeof(B[0]);
printAnswer(A, B, n, m);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
static int MAX = 26;
// Function to count the number of smaller
// strings in A[] for every String in B[]
static Vector<Integer> findCount(String a[],
String b[],
int n, int m)
{
// Count the frequency of all characters
int []freq = new int[MAX];
Vector<Integer> smallestFreq = new Vector<Integer>();
// Iterate for all possible strings in A[]
for (int i = 0; i < n; i++)
{
String s = a[i];
Arrays.fill(freq, 0);
// Increase the frequency of every character
for (int j = 0; j < s.length(); j++)
{
freq[s.charAt(j) - 'a']++;
}
// Check for the smallest character's frequency
for (int j = 0; j < MAX; j++)
{
// Get the smallest character frequency
if (freq[j] > 0)
{
// Insert it in the vector
smallestFreq.add(freq[j]);
break;
}
}
}
// Sort the count of all the frequency of
// the smallest character in every string
Collections.sort(smallestFreq);
Vector<Integer> ans = new Vector<Integer>();
// Iterate for every String in B[]
for (int i = 0; i < m; i++)
{
String s = b[i];
// Hash set every frequency 0
Arrays.fill(freq, 0);
// Count the frequency of every character
for (int j = 0; j < s.length(); j++)
{
freq[s.charAt(j) - 'a']++;
}
int frequency = 0;
// Find the frequency of the smallest character
for (int j = 0; j < MAX; j++)
{
if (freq[j] > 0)
{
frequency = freq[j];
break;
}
}
// Count the number of strings in A[]
// which has the frequency of the smaller
// character less than the frequency of the
// smaller character of the String in B[]
int [] array = new int[smallestFreq.size()];
int k = 0;
for(Integer val:smallestFreq)
{
array[k] = val;
k++;
}
int ind = lower_bound(array, 0,
smallestFreq.size(),
frequency);
// Store the answer
ans.add(ind);
}
return ans;
}
static int lower_bound(int[] a, int low,
int high, int element)
{
while(low < high)
{
int middle = low + (high - low) / 2;
if(element > a[middle])
low = middle + 1;
else
high = middle;
}
return low;
}
// Function to print the answer
static void printAnswer(String a[], String b[],
int n, int m)
{
// Get the answer
Vector<Integer> ans = findCount(a, b, n, m);
// Print the number of strings
// for every answer
for (Integer it : ans)
{
System.out.print(it + " ");
}
}
// Driver code
public static void main(String[] args)
{
String A[] = { "aaa", "aa", "bdc" };
String B[] = { "cccch", "cccd" };
int n = A.length;
int m = B.length;
printAnswer(A, B, n, m);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the approach
from bisect import bisect_left as lower_bound
MAX = 26
# Function to count the number of smaller
# strings in A for every in B
def findCount(a, b, n, m):
# Count the frequency of all characters
freq=[0 for i in range(MAX)]
smallestFreq=[]
# Iterate for all possible strings in A
for i in range(n):
s = a[i]
for i in range(MAX):
freq[i]=0
# Increase the frequency of every character
for j in range(len(s)):
freq[ord(s[j]) - ord('a')]+= 1
# Check for the smallest character's frequency
for j in range(MAX):
# Get the smallest character frequency
if (freq[j]):
# Insert it in the vector
smallestFreq.append(freq[j])
break
# Sort the count of all the frequency of the smallest
# character in every string
smallestFreq=sorted(smallestFreq)
ans=[]
# Iterate for every in B
for i in range(m):
s = b[i]
# Hash set every frequency 0
for i in range(MAX):
freq[i]=0
# Count the frequency of every character
for j in range(len(s)):
freq[ord(s[j]) - ord('a')]+= 1
frequency = 0
# Find the frequency of the smallest character
for j in range(MAX):
if (freq[j]):
frequency = freq[j]
break
# Count the number of strings in A
# which has the frequency of the smaller
# character less than the frequency of the
# smaller character of the in B
ind = lower_bound(smallestFreq,frequency)
# Store the answer
ans.append(ind)
return ans
# Function to print the answer
def printAnswer(a, b, n, m):
# Get the answer
ans = findCount(a, b, n, m)
# Print the number of strings
# for every answer
for it in ans:
print(it,end=" ")
# Driver code
A = ["aaa", "aa", "bdc"]
B = ["cccch", "cccd"]
n = len(A)
m = len(B)
printAnswer(A, B, n, m)
# This code is contributed by mohit kumar 29
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
public class GFG
{
static int MAX = 26;
// Function to count the number of smaller
// strings in A[] for every String in B[]
static List<int> findCount(String []a,
String []b,
int n, int m)
{
// Count the frequency of all characters
int []freq = new int[MAX];
List<int> smallestFreq = new List<int>();
// Iterate for all possible strings in A[]
for (int i = 0; i < n; i++)
{
String s = a[i];
for (int l = 0; l < freq.Length; l++)
freq[l]=0;
// Increase the frequency of every character
for (int j = 0; j < s.Length; j++)
{
freq[s[j] - 'a']++;
}
// Check for the smallest character's frequency
for (int j = 0; j < MAX; j++)
{
// Get the smallest character frequency
if (freq[j] > 0)
{
// Insert it in the vector
smallestFreq.Add(freq[j]);
break;
}
}
}
// Sort the count of all the frequency of
// the smallest character in every string
smallestFreq.Sort();
List<int> ans = new List<int>();
// Iterate for every String in B[]
for (int i = 0; i < m; i++)
{
String s = b[i];
// Hash set every frequency 0
for (int l = 0; l < freq.Length; l++)
freq[l]=0;
// Count the frequency of every character
for (int j = 0; j < s.Length; j++)
{
freq[s[j] - 'a']++;
}
int frequency = 0;
// Find the frequency of the smallest character
for (int j = 0; j < MAX; j++)
{
if (freq[j] > 0)
{
frequency = freq[j];
break;
}
}
// Count the number of strings in A[]
// which has the frequency of the smaller
// character less than the frequency of the
// smaller character of the String in B[]
int [] array = new int[smallestFreq.Count];
int k = 0;
foreach (int val in smallestFreq)
{
array[k] = val;
k++;
}
int ind = lower_bound(array, 0,
smallestFreq.Count,
frequency);
// Store the answer
ans.Add(ind);
}
return ans;
}
static int lower_bound(int[] a, int low,
int high, int element)
{
while(low < high)
{
int middle = low + (high - low) / 2;
if(element > a[middle])
low = middle + 1;
else
high = middle;
}
return low;
}
// Function to print the answer
static void printAnswer(String []a, String []b,
int n, int m)
{
// Get the answer
List<int> ans = findCount(a, b, n, m);
// Print the number of strings
// for every answer
foreach (int it in ans)
{
Console.Write(it + " ");
}
}
// Driver code
public static void Main(String[] args)
{
String []A = { "aaa", "aa", "bdc" };
String []B = { "cccch", "cccd" };
int n = A.Length;
int m = B.Length;
printAnswer(A, B, n, m);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript implementation of the approach
const MAX = 26;
// Function to count the number of smaller
// strings in A[] for every String in B[]
function findCount(a, b, n, m)
{
// Count the frequency of all characters
var freq = new Array(MAX).fill(0);
var smallestFreq = [];
// Iterate for all possible strings in A[]
for(var i = 0; i < n; i++)
{
var s = a[i];
for(var l = 0; l < freq.length; l++)
freq[l] = 0;
// Increase the frequency of every character
for(var j = 0; j < s.length; j++)
{
freq[s[j].charCodeAt(0) -
"a".charCodeAt(0)]++;
}
// Check for the smallest character's frequency
for(var j = 0; j < MAX; j++)
{
// Get the smallest character frequency
if (freq[j] > 0)
{
// Insert it in the vector
smallestFreq.push(freq[j]);
break;
}
}
}
// Sort the count of all the frequency of
// the smallest character in every string
smallestFreq.sort();
var ans = [];
// Iterate for every String in B[]
for(var i = 0; i < m; i++)
{
var s = b[i];
// Hash set every frequency 0
for(var l = 0; l < freq.length; l++)
freq[l] = 0;
// Count the frequency of every character
for(var j = 0; j < s.length; j++)
{
freq[s[j].charCodeAt(0) -
"a".charCodeAt(0)]++;
}
var frequency = 0;
// Find the frequency of the smallest character
for(var j = 0; j < MAX; j++)
{
if (freq[j] > 0)
{
frequency = freq[j];
break;
}
}
// Count the number of strings in A[]
// which has the frequency of the smaller
// character less than the frequency of the
// smaller character of the String in B[]
var array = new Array(smallestFreq.length).fill(0);
var k = 0;
for(const val of smallestFreq)
{
array[k] = val;
k++;
}
var ind = lower_bound(
array, 0, smallestFreq.length, frequency);
// Store the answer
ans.push(ind);
}
return ans;
}
function lower_bound(a, low, high, element)
{
while (low < high)
{
var middle = low + parseInt((high - low) / 2);
if (element > a[middle])
low = middle + 1;
else
high = middle;
}
return low;
}
// Function to print the answer
function printAnswer(a, b, n, m)
{
// Get the answer
var ans = findCount(a, b, n, m);
// Print the number of strings
// for every answer
for(const it of ans)
{
document.write(it + " ");
}
}
// Driver code
var A = [ "aaa", "aa", "bdc" ];
var B = [ "cccch", "cccd" ];
var n = A.length;
var m = B.length;
printAnswer(A, B, n, m);
// This code is contributed by rdtank
</script>
Producción:
3 2
Complejidad de tiempo: O(n *(log(n) + m)), donde n es el tamaño de la array y m es la longitud máxima de una string en la array.
Espacio Auxiliar: O(26)