Dadas dos strings ‘S1’ y ‘S2’, la tarea es devolver la palabra más frecuente (que se usa el número máximo de veces) de ‘S1’ que no está presente en ‘S2’. Si es posible más de una palabra, escriba lexicográficamente la más pequeña entre ellas.
Ejemplos:
Entrada: S1 = “geeks para geeks es el mejor lugar para aprender”, S2 = “mal lugar”
Salida: geeks
“geeks” es la palabra más frecuente en S1 y tampoco está presente en S2.
La frecuencia de “geeks” es 2
Entrada: S1 = “el veloz zorro marrón salta sobre el perro perezoso”, S2 = “el zorro marrón salta”
Salida: perro
Todas las palabras tienen frecuencia 1.
La palabra lexicográficamente más pequeña es “perro”
Enfoque: el proceso de pensamiento debe comenzar con la creación de un mapa para almacenar el par clave-valor (string, int). A continuación, comienza la extracción de las palabras de la primera string mientras se actualiza el mapa y el conteo. Por cada palabra de la segunda array que esté presente en la primera array, restablezca el conteo. Finalmente, recorra el mapa y encuentre la palabra con la frecuencia más alta y obtenga la lexicográficamente más pequeña.
Algoritmo:
- Itere a través de la string S2 y cree un mapa e inserte todas las palabras en él en el mapa.
- Iterar a través de la string S1 y verificar si la palabra no está presente en el mapa creado en el paso anterior o no.
- Si la palabra cumple la condición, actualice la respuesta si la frecuencia de la misma palabra es máxima hasta ahora.
- Si la frecuencia de la palabra es igual a la palabra elegida previamente, actualice la respuesta de acuerdo con la lexicografía más pequeña de las dos strings.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return frequent
// word from S1 that isn't
// present in S2
string smallestFreq(string S1, string S2)
{
map<string, int> banned;
// create map of banned words
for (int i = 0; i < S2.length(); ++i) {
string s = "";
while (i < S2.length() && S2[i] != ' ')
s += S2[i++];
banned[s]++;
}
map<string, int> result;
string ans;
int freq = 0;
// find smallest and most frequent word
for (int i = 0; i < S1.length(); ++i) {
string s = "";
while (i < S1.length() && S1[i] != ' ')
s += S1[i++];
// check if word is not banned
if (banned[s] == 0) {
result[s]++;
if (result[s] > freq
|| (result[s] == freq && s < ans)) {
ans = s;
freq = result[s];
}
}
}
// return answer
return ans;
}
// Driver program
int main()
{
string S1 = "geeks for geeks is best place to learn";
string S2 = "bad place";
cout << smallestFreq(S1, S2);
return 0;
}
Java
// Java implementation of above approach
import java.util.HashMap;
class GFG
{
// Function to return frequent
// word from S1 that isn't
// present in S2
static String smallestFreq(String S1,
String S2)
{
HashMap<String,
Integer> banned = new HashMap<>();
// create map of banned words
for (int i = 0; i < S2.length(); i++)
{
String s = "";
while (i < S2.length() &&
S2.charAt(i) != ' ')
s += S2.charAt(i++);
banned.put(s, banned.get(s) == null ?
1 : banned.get(s) + 1);
}
HashMap<String,
Integer> result = new HashMap<>();
String ans = "";
int freq = 0;
// find smallest and most frequent word
for (int i = 0; i < S1.length(); i++)
{
String s = "";
while (i < S1.length() &&
S1.charAt(i) != ' ')
s += S1.charAt(i++);
// check if word is not banned
if (banned.get(s) == null)
{
result.put(s, result.get(s) == null ? 1 :
result.get(s) + 1);
if (result.get(s) > freq ||
(result.get(s) == freq &&
s.compareTo(ans) < 0))
{
ans = s;
freq = result.get(s);
}
}
}
// return answer
return ans;
}
// Driver Code
public static void main(String[] args)
{
String S1 = "geeks for geeks is best place to learn";
String S2 = "bad place";
System.out.println(smallestFreq(S1, S2));
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 implementation of above approach from collections import defaultdict # Function to return frequent # word from S1 that isn't # present in S2 def smallestFreq(S1, S2): banned = defaultdict(lambda:0) i = 0 # create map of banned words while i < len(S2): s = "" while i < len(S2) and S2[i] != ' ': s += S2[i] i += 1 i += 1 banned[s] += 1 result = defaultdict(lambda:0) ans = "" freq = 0 i = 0 # find smallest and most frequent word while i < len(S1): s = "" while i < len(S1) and S1[i] != ' ': s += S1[i] i += 1 i += 1 # check if word is not banned if banned[s] == 0: result[s] += 1 if (result[s] > freq or (result[s] == freq and s < ans)): ans = s freq = result[s] # return answer return ans # Driver Code if __name__ == "__main__": S1 = "geeks for geeks is best place to learn" S2 = "bad place" print(smallestFreq(S1, S2)) # This code is contributed # by Rituraj Jain
C#
// C# implementation of above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to return frequent
// word from S1 that isn't
// present in S2
static String smallestFreq(String S1,
String S2)
{
Dictionary<String,
int> banned = new Dictionary<String,
int>();
// create map of banned words
for (int i = 0; i < S2.Length; i++)
{
String s = "";
while (i < S2.Length &&
S2[i] != ' ')
s += S2[i++];
if(banned.ContainsKey(s))
{
var val = banned[s];
banned.Remove(s);
banned.Add(s, val + 1);
}
else
{
banned.Add(s, 1);
}
}
Dictionary<String,
int> result = new Dictionary<String,
int>();
String ans = "";
int freq = 0;
// find smallest and most frequent word
for (int i = 0; i < S1.Length; i++)
{
String s = "";
while (i < S1.Length &&
S1[i] != ' ')
s += S1[i++];
// check if word is not banned
if (!banned.ContainsKey(s))
{
if(result.ContainsKey(s))
{
var val = result[s];
result.Remove(s);
result.Add(s, val + 1);
}
else
{
result.Add(s, 1);
}
if (result[s] > freq ||
(result[s] == freq &&
s.CompareTo(ans) < 0))
{
ans = s;
freq = result[s];
}
}
}
// return answer
return ans;
}
// Driver Code
public static void Main(String[] args)
{
String S1 = "geeks for geeks is best place to learn";
String S2 = "bad place";
Console.WriteLine(smallestFreq(S1, S2));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript implementation of above approach
// Function to return frequent
// word from S1 that isn't
// present in S2
function smallestFreq(S1,S2)
{
let banned = new Map();
// create map of banned words
for (let i = 0; i < S2.length; i++)
{
let s = "";
while (i < S2.length &&
S2[i] != ' ')
s += S2[i++];
banned.set(s, banned[s] == null ?
1 : banned.get(s) + 1);
}
let result = new Map();
let ans = "";
let freq = 0;
// find smallest and most frequent word
for (let i = 0; i < S1.length; i++)
{
let s = "";
while (i < S1.length &&
S1[i] != ' ')
s += S1[i++];
// check if word is not banned
if (banned.get(s) == null)
{
result.set(s, result.get(s) == null ? 1 :
result.get(s) + 1);
if (result.get(s) > freq ||
(result.get(s) == freq &&
s < (ans) ))
{
ans = s;
freq = result.get(s);
}
}
}
// return answer
return ans;
}
// Driver Code
let S1 = "geeks for geeks is best place to learn";
let S2 = "bad place";
document.write(smallestFreq(S1, S2));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
geeks
Análisis de Complejidad:
- Complejidad de tiempo: O(n), donde n es la longitud de la string.
Se necesita un solo recorrido de la string. - Complejidad espacial: O(n).
Puede haber como máximo n palabras en una string. El mapa requiere espacio O(n) para almacenar las strings.
Publicación traducida automáticamente
Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA