Dada una lista de caracteres y una array de strings , encuentre la longitud total de todas las strings en la array de strings que se pueden componer usando los caracteres dados.
Ejemplos:
Entrada: string = [“ratón”, “yo”, “murciélago”, “león”], chars = “eusamotb”
Salida: 10
Explicación:
Las strings que se pueden formar usando los caracteres “eusamotb” son “mouse” y “ yo” y “murciélago”.
La longitud de «ratón» es 5, la longitud de «yo» es 2 y la longitud de «murciélago» es 3
Suma de todas las longitudes = 5 + 2 + 3 = 10.
Entrada: string = [“hola”, “datos”, “geeksforgeeks”], chars = “tiadha”
Salida: 6
Explicación:
Las strings que se pueden formar usando los caracteres “tiadha” son “hola” y “datos”. Donde la longitud de «hola» es 2, la longitud de «datos» es 4, la suma de todos es 2 + 4 = 6.
Enfoque:
Para resolver el problema mencionado anteriormente, debemos seguir los pasos que se detallan a continuación:
- Podemos usar caracteres de la string de caracteres dada que es ‘chars’ mientras formamos una string. También podemos reutilizar los caracteres usados para formar la siguiente string.
- Mantenga un mapa desordenado con el carácter como clave y el valor realizando un seguimiento de la frecuencia de cada carácter de la string de caracteres.
- Cada vez que escaneamos caracteres de la lista de strings, reducimos la frecuencia de caracteres del mapa desordenado, pero debemos mantener la copia del mapa original para verificar la segunda string.
- Si la clave no está presente en el mapa, crea una con un valor predeterminado de cero en lugar de arrojar un error.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find total length
// of string composed of given characters
// formed from given Array of strings
#include <bits/stdc++.h>
using namespace std;
// Function to count the total length
int countCharacters(
vector<string>& strings,
string chars)
{
int res = 0;
// Unordered_map for
// keeping frequency of characters
unordered_map<char, int> freq;
// Calculate the frequency
for (int i = 0; i < chars.length(); i++)
freq[chars[i]] += 1;
// Iterate in the N strings
for (auto st : strings) {
bool flag = true;
// Iterates in the string
for (auto c : st) {
// Checks if given character of string
// string appears in it or not
if (!freq) {
flag = false;
break;
}
}
// Adds the length of string
// if all characters are present
if (flag)
res += st.length();
}
// Return the final result
return res;
}
// Driver code
int main()
{
vector<string> strings
= { "hi", "data",
"geeksforgeeks" };
string chars = "tiadhae";
cout << countCharacters(strings, chars);
return 0;
}
Java
// Java implementation to find total length
// of string composed of given characters
// formed from given Array of strings
import java.util.*;
class GFG {
// Function to count the total length
static int countCharacters(List<String> strings,
String chars)
{
int res = 0;
// Map for
// keeping frequency of characters
Map<Character, Integer> freq = new HashMap<>();
// Calculate the frequency
for (int i = 0; i < chars.length(); i++)
{
freq.put(chars.charAt(i),
freq.getOrDefault(chars.charAt(i), 0) + 1);
}
// Iterate in the N strings
for (String st : strings)
{
boolean flag = true;
// Iterates in the string
for (char c : st.toCharArray())
{
// Checks if given character of string
// string appears in it or not
if (!freq.containsKey(c))
{
flag = false;
break;
}
}
// Adds the length of string
// if all characters are present
if (flag)
res += st.length();
}
// Return the final result
return res;
}
// Driver code
public static void main(String[] args)
{
List<String> strings = Arrays.asList("hi", "data",
"geeksforgeeks");
String chars = "tiadhae";
System.out.println(countCharacters(strings, chars));
}
}
// This code is contributed by offbeat
Python3
# Python3 implementation to find total length # of string composed of given characters # formed from given Array of strings # Function to count the total length def countCharacters(arr, chars): res = 0 # Unordered_map for # keeping frequency of characters freq = dict() # Calculate the frequency for i in range(len(chars)): freq[chars[i]] = freq.get(chars[i], 0)+1 # Iterate in the N strings for st in arr: flag = True # Iterates in the string for c in st: # Checks if given character of string # string appears in it or not if (c not in freq): flag = False break # Adds the length of string # if all characters are present if (flag): res += len(st) # Return the final result return res # Driver code if __name__ == '__main__': arr =["hi", "data", "geeksforgeeks"] chars = "tiadhae" print(countCharacters(arr, chars)) # This code is contributed by mohit kumar 29
C#
// C# implementation to find total length
// of string composed of given characters
// formed from given Array of strings
using System;
using System.Collections.Generic;
using System.Linq;
class GFG{
// Function to count the total length
static int countCharacters(List<string> strings,
string chars)
{
int res = 0;
// Dictionary for keeping frequency
// of characters
Dictionary<char,
int> freq = new Dictionary<char,
int>();
// Calculate the frequency
for(int i = 0; i < chars.Length; i++)
{
if(freq.ContainsKey(chars[i]))
{
freq[chars[i]]++;
}
else
{
freq.Add(chars[i],
freq.GetValueOrDefault(
chars[i], 0) + 1);
}
}
// Iterate in the N strings
foreach(string st in strings)
{
bool flag = true;
// Iterates in the string
foreach (char c in st.ToCharArray())
{
// Checks if given character of string
// string appears in it or not
if (!freq.ContainsKey(c))
{
flag = false;
break;
}
}
// Adds the length of string
// if all characters are present
if (flag)
res += st.Length;
}
// Return the final result
return res;
}
// Driver code
public static void Main(string[] args)
{
string []tmp = { "hi", "data",
"geeksforgeeks" };
List<string> strings = tmp.ToList();
string chars = "tiadhae";
Console.Write(countCharacters(strings, chars));
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript implementation to find total length
// of string composed of given characters
// formed from given Array of strings
// Function to count the total length
function countCharacters( strings, chars)
{
var res = 0;
// Unordered_map for
// keeping frequency of characters
var freq = new Map();
// Calculate the frequency
for (var i = 0; i < chars.length; i++)
{
if(freq.has(chars[i]))
freq.set(chars[i], freq.get(chars[i])+1)
else
freq.set(chars[i], 1)
}
// Iterate in the N strings
strings.forEach(st => {
var flag = true;
// Iterates in the string
st.split('').forEach(c => {
// Checks if given character of string
// string appears in it or not
if (!freq.has(c)) {
flag = false;
}
});
// Adds the length of string
// if all characters are present
if (flag)
res += st.length;
});
// Return the final result
return res;
}
// Driver code
var strings
= ["hi", "data",
"geeksforgeeks"];
var chars = "tiadhae";
document.write( countCharacters(strings, chars));
// This code is contributed by noob2000.
</script>
Producción:
6
Complejidad de tiempo: O(n * m) , donde n es la longitud del carácter y m es la longitud de la string.
Complejidad del Espacio Auxiliar: O(1) , ya que el mapa desordenado será de tamaño 26 solamente.