Dadas dos strings str1 y str2 , la tarea es imprimir el número de veces que se puede formar str2 usando caracteres de str1 . Sin embargo, un carácter en cualquier índice de str1 solo se puede usar una vez en la formación de str2 .
Ejemplos:
Entrada: str1 = “arajjhupoot”, str2 = “rajput”
Salida: 1
Explicación:
str2 solo se puede formar una vez usando los caracteres de str1.Entrada: str1 = «foreeksgekseg», str2 = «geeks»
Salida: 2
Enfoque: dado que el problema tiene una restricción en el uso de caracteres de str1 solo una vez para formar str2 . Si se ha usado un carácter para formar una str2 , no se puede usar para formar otra str2 . Cada carácter de str2 debe estar presente en str1 al menos para la formación de un str1 . Si todos los caracteres de str2 ya están presentes en str1 , entonces el carácter que tiene la mínima ocurrencia en str1 será el número de str2 que se pueden formar usando los caracteres de str1 una vez. A continuación se muestran los pasos:
- Cree una array hash que almacene el número de ocurrencias de cada carácter de str1 y str2 .
- Iterar para todos los caracteres de str2 y encontrar el mínimo de ocurrencias de cada carácter en str1 .
- Devuelve la ocurrencia mínima que será la respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++14
/// C++ program to print the number of times
// str2 can be formed from str1 using the
// characters of str1 only once
#include <bits/stdc++.h>
using namespace std;
// Function to find the number of str2
// that can be formed using characters of str1
int findNumberOfTimes(string str1, string str2)
{
int freq[26] = { 0 };
int freq2[26] = { 0 };
int l1 = str1.length();
int l2 = str2.length();
// iterate and mark the frequencies of
// all characters in str1
for (int i = 0; i < l1; i++)
freq[str1[i] - 'a'] += 1;
for (int i = 0; i < l2; i++)
freq2[str2[i] - 'a'] += 1;
int count = INT_MAX;
// find the minimum frequency of
// every character in str1
for (int i = 0; i < l2; i++)
{
if(freq2[str2[i]-'a']!=0)
count = min(count, freq[str2[i] - 'a']/freq2[str2[i]-'a']);
}
return count;
}
// Driver Code
int main()
{
string str1 = "foreeksgekseg";
string str2 = "geeks";
cout << findNumberOfTimes(str1, str2)
<< endl;
return 0;
}
Java
// Java program to print the number of times
// str2 can be formed from str1 using the
// characters of str1 only once
class GFG {
// Function to find the number of str2
// that can be formed using characters of str1
static int findNumberOfTimes(String str1, String str2)
{
int freq[] = new int[26];
int freq2[] = new int[26];
int l1 = str1.length();
// iterate and mark the frequencies of
// all characters in str1
for (int i = 0; i < l1; i++)
{
freq[str1.charAt(i) - 'a'] += 1;
}
int l2 = str2.length();
for (int i = 0; i < l2; i++)
{
freq2[str2.charAt(i) - 'a'] += 1;
}
int count = Integer.MAX_VALUE;
// find the minimum frequency of
// every character in str1
for (int i = 0; i < l2; i++)
{
if(freq2[str2.charAt(i)-'a']!=0)
count = Math.min(count,
freq[str2.charAt(i) - 'a']/freq2[str2.charAt(i)-'a']);
}
return count;
}
public static void main(String[] args) {
String str1 = "foreeksgekseg";
String str2 ="geeks";
System.out.println(findNumberOfTimes(str1, str2));
}
}
/* This code is contributed by 29AjayKumar*/
Python3
# Python3 program to print the number of
# times str2 can be formed from str1 using
# the characters of str1 only once
import sys
# Function to find the number of str2
# that can be formed using characters of str1
def findNumberOfTimes(str1, str2):
freq = [0] * 26
l1 = len(str1)
freq2= [0] * 26
l2 = len(str2)
# iterate and mark the frequencies
# of all characters in str1
for i in range(l1):
freq[ord(str1[i]) - ord("a")] += 1
for i in range(l2):
freq2[ord(str2[i]) - ord("a")] += 1
count = sys.maxsize
# find the minimum frequency of
# every character in str1
for i in range(l2):
count = min(count, freq[ord(str2[i])
- ord('a')]/freq2[ord(str2[i])-ord('a')])
return count
# Driver Code
if __name__ == '__main__':
str1 = "foreeksgekseg"
str2 = "geeks"
print(findNumberOfTimes(str1, str2))
# This code is contributed by PrinciRaj1992
C#
// C# program to print the number of
// times str2 can be formed from str1
// using the characters of str1 only once
using System;
class GFG {
// Function to find the number of
// str2 that can be formed using
// characters of str1
static int findNumberOfTimes(String str1, String str2)
{
int[] freq = new int[26];
int l1 = str1.Length;
int[] freq2 = new int[26];
int l2 = str2.Length;
// iterate and mark the frequencies
// of all characters in str1
for (int i = 0; i < l1; i++)
{
freq[str1[i] - 'a'] += 1;
}
for (int i = 0; i < l2; i++)
{
freq2[str2[i] - 'a'] += 1;
}
int count = int.MaxValue;
// find the minimum frequency of
// every character in str1
for (int i = 0; i < l2; i++)
{
if (freq2[str2[i] - 'a'] != 0)
count = Math.Min(
count, freq[str2[i] - 'a']
/ freq2[str2[i] - 'a']);
}
return count;
}
// Driver Code
public static void Main()
{
String str1 = "foreeksgekseg";
String str2 = "geeks";
Console.Write(findNumberOfTimes(str1, str2));
}
}
// This code is contributed by 29AjayKumar
PHP
<?php
// PHP program to print the number of times
// str2 can be formed from str1 using the
// characters of str1 only once
// Function to find the number of str2
// that can be formed using characters of str1
function findNumberOfTimes($str1, $str2)
{
$freq = array_fill(0, 26, NULL);
$l1 = strlen($str1);
$freq2 = array_fill(0, 26, NULL);
$l2 = strlen($str2);
// iterate and mark the frequencies
// of all characters in str1
for ($i = 0; $i < $l1; $i++)
$freq[ord($str1[$i]) - ord('a')] += 1;
for ($i = 0; $i < $l2; $i++)
$freq2[ord($str2[$i]) - ord('a')] += 1;
$count = PHP_INT_MAX;
// find the minimum frequency of
// every character in str1
for ($i = 0; $i < $l2; $i++)
$count = min($count, $freq[ord($str2[$i]) -
ord('a')]/$freq2[ord($str2[$i]) -
ord('a')]);
return $count;
}
// Driver Code
$str1 = "foreeksgekseg";
$str2 = "geeks";
echo findNumberOfTimes($str1, $str2) . "\n";
// This code is contributed by ita_c
?>
Javascript
<script>
// Javascript program to print the number of times
// str2 can be formed from str1 using the
// characters of str1 only once
// Function to find the number of str2
// that can be formed using characters of str1
function findNumberOfTimes(str1, str2)
{
let freq = new Array(26);
let freq2 = new Array(26);
for(let i = 0; i < 26; i++)
{
freq[i] = 0;
freq2[i] = 0;
}
let l1 = str1.length;
// iterate and mark the frequencies of
// all characters in str1
for (let i = 0; i < l1; i++)
{
freq[str1[i].charCodeAt(0) - 'a'.charCodeAt(0)] += 1;
}
let l2 = str2.length;
for (let i = 0; i < l2; i++)
{
freq2[str2[i].charCodeAt(0) - 'a'.charCodeAt(0)] += 1;
}
let count = Number.MAX_VALUE;
// find the minimum frequency of
// every character in str1
for (let i = 0; i < l2; i++)
{
if(freq2[str2[i].charCodeAt(0)-'a'.charCodeAt(0)]!=0)
count = Math.min(count,
freq[str2[i].charCodeAt(0) - 'a'.charCodeAt(0)]/freq2[str2[i].charCodeAt(0)-'a'.charCodeAt(0)]);
}
return count;
}
let str1 = "foreeksgekseg";
let str2 ="geeks";
document.write(findNumberOfTimes(str1, str2));
// This code is contributed by avanitrachhadiya2155
</script>
Producción
2
Complejidad de tiempo: O(l1+l2), donde l1 y l2 son la longitud de str1 y str2 respectivamente.
Espacio Auxiliar: O(1)
Caso: uso de mapas STL con caracteres en mayúsculas y minúsculas en str1 y str2.
Enfoque: El funcionamiento es similar al hash-array normal .
Aquí, el orden no importa. Solo necesitamos verificar si hay suficientes palabras en str1 para hacer str2 . Atraviese las strings str1 y str2 para almacenar caracteres como clave y sus frecuencias como valor en los mapas freq1 y freq2 . Divida las frecuencias almacenadas en map freq1 con frecuencias que tengan una clave coincidente en map freq2 . Esto nos dará el número máximo de ciclos de str2 que se pueden formar. Finalmente, devuelva la frecuencia mínima del mapa freq1 , que será la respuesta final.
C++14
#include <bits/stdc++.h>
using namespace std;
int countSubStr(char* str,char* substr)
{
unordered_map<char,int>freq1;
unordered_map<char,int>freq2;
int i,mn=INT_MAX;
int l1=strlen(str);
int l2=strlen(substr);
for(i=0;i<l1;i++)
freq1[str[i]]++;
for(i=0;i<l2;i++)
freq2[substr[i]]++;
for(auto x:freq2)
mn=min(mn,freq1[x.first]/x.second);
return mn;
}
int main()
{
char str1[]= "arajjhupoot";
char str2[]="rajput";
cout<<countSubStr(str1,str2);
return 0;
}
Java
// java implementation to find sum of
// first n even numbers
import java.io.*;
import java.util.*;
class GFG
{
public static int countSubStr(String str,String substr)
{
HashMap<Character, Integer> freq1 = new HashMap<>();
HashMap<Character, Integer> freq2 = new HashMap<>();
int i, mn = Integer.MAX_VALUE;
int l1 = str.length();
int l2 = substr.length();
for(int idx = 0; idx < str.length(); idx++){
char c = str.charAt(idx);
if (freq1.containsKey(c)) {
freq1.put(c, freq1.get(c) + 1);
}
else {
freq1.put(c, 1);
}
}
for(int idx = 0; idx < substr.length(); idx++) {
char c = substr.charAt(idx);
if (freq2.containsKey(c)) {
freq2.put(c, freq2.get(c) + 1);
}
else {
freq2.put(c, 1);
}
}
for (Map.Entry mapElement : freq2.entrySet()) {
char first = (char)mapElement.getKey();
int second = (int)mapElement.getValue();
int second_f1 = freq1.get(first);
mn = Math.min(mn,second_f1/second);
}
return mn;
}
// Driver program to test above
public static void main(String[] args)
{
String str1= "arajjhupoot";
String str2="rajput";
System.out.println(countSubStr(str1,str2));
}
}
// This code is contributed by aditya942003patil
Javascript
<script>
function countSubStr(str,substr)
{
let freq1 = new Map();
let freq2 = new Map();
let i,mn=Number.MAX_VALUE;
let l1 = str.length;
let l2 = substr.length;
for(i = 0; i < l1; i++){
if(freq1.has(str[i]) == true){
freq1.set(str[i], freq1.get(str[i]) + 1);
}
else{
freq1.set(str[i], 1);
}
}
for(i = 0; i < l2; i++){
if(freq2.has(substr[i]) == true){
freq2.set(substr[i], freq1.get(str[i]) + 1);
}
else{
freq2.set(substr[i], 1);
}
}
for(let [x, y] of freq2)
mn = Math.min(mn,Math.floor(freq1.get(x)/y));
return mn;
}
// driver code
let str1 = "arajjhupoot";
let str2 ="rajput";
document.write(countSubStr(str1,str2));
// This code is contributed by shinjanpatra
</script>
Python3
from math import floor
import sys
def countSubStr(str,substr):
freq1 = {}
freq2 = {}
mn = sys.maxsize
l1 = len(str)
l2 = len(substr)
for i in range(l1):
if(str[i] in freq1):
freq1[str[i]] = freq1[str[i]] + 1
else:
freq1[str[i]] = 1
for i in range(l2):
if substr[i] in freq2:
freq2[substr[i]] = freq1[str[i]] + 1
else:
freq2[substr[i]] = 1
for x, y in freq2.items():
mn = min(mn,floor(freq1[x]/y))
return mn
# driver code
str1 = "arajjhupoot"
str2 ="rajput"
print(countSubStr(str1,str2))
# This code is contributed by shinjanpatra
Salida : 1
Complejidad de tiempo: O(l1+l2), donde l1 y l2 son la longitud de str1 y str2 respectivamente
Espacio auxiliar: O(1) ya que el número total de caracteres distintos en alfabetos ingleses tanto en minúsculas como en mayúsculas es 52 (Constante) .