Dada una string S y un número entero N , la tarea es verificar si es posible generar cualquier string N veces a partir de los caracteres de la string dada o no. Si es posible, escriba Sí . De lo contrario , imprima No.
Ejemplos:
Entrada: S = “caacbb”, N = 2
Salida: Sí
Explicación: Todas las strings posibles que se pueden generar N(= 2) veces son {“abc”, “ab”, “aa”, “bb”, “cc” , “bc”, “ca”}Entrada: S = “cbacbac”, N = 3
Salida: No
Explicación: Dado que ninguno de los caracteres aparece N veces, no se puede generar una string N veces a partir de los caracteres de la string dada.
Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todas las permutaciones posibles de todas las longitudes posibles de la string dada y verificar si alguna permutación ocurre N veces o no. Si es cierto, escriba » Sí» . De lo contrario, escriba “ No”
Complejidad de tiempo: O(N*L!), donde L es la longitud de la string dada.
Espacio Auxiliar: O(L)
Enfoque eficiente: la idea es almacenar la frecuencia de todos los caracteres y contar el número de caracteres que aparecen al menos N veces. Siga los pasos a continuación para resolver el problema:
- Almacene las frecuencias de cada carácter de la string en una array, digamos freq[] .
- Recorra la array freq[] y para cada i -ésimo carácter, verifique si freq[i] >= N o no.
- Si se encuentra que algún carácter cumple con la condición anterior, imprima Sí . De lo contrario , imprima No.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if the freq of
// any character is divisible by N
bool isSame(string str, int n)
{
// Stores the frequency of characters
map<int, int> mp;
for (int i = 0; i < str.length(); i++) {
mp[str[i] - 'a']++;
}
for (auto it : mp) {
// If frequency of a character
// is not divisible by n
if ((it.second) >= n) {
return true;
}
}
// If no character has frequency
// at least N
return false;
}
// Driver Code
int main()
{
string str = "ccabcba";
int n = 4;
// Function Call
if (isSame(str, n)) {
cout << "Yes";
}
else {
cout << "No";
}
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to check if the freq of
// any character is divisible by N
static boolean isSame(String str, int n)
{
// Stores the frequency of characters
HashMap<Integer,
Integer> mp = new HashMap<Integer,
Integer>();
for (int i = 0; i < str.length(); i++)
{
if(mp.containsKey(str.charAt(i) - 'a'))
{
mp.put(str.charAt(i) - 'a',
mp.get(str.charAt(i) - 'a') + 1);
}
else
{
mp.put(str.charAt(i) - 'a', 1);
}
}
for (Map.Entry<Integer, Integer> it : mp.entrySet())
{
// If frequency of a character
// is not divisible by n
if ((it.getValue()) >= n)
{
return true;
}
}
// If no character has frequency
// at least N
return false;
}
// Driver Code
public static void main(String[] args)
{
String str = "ccabcba";
int n = 4;
// Function Call
if (isSame(str, n))
{
System.out.print("Yes");
}
else
{
System.out.print("No");
}
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program for the above approach
from collections import defaultdict
# Function to check if the freq of
# any character is divisible by N
def isSame(str, n):
# Stores the frequency of characters
mp = defaultdict(lambda : 0)
for i in range(len(str)):
mp[ord(str[i]) - ord('a')] += 1
for it in mp.keys():
# If frequency of a character
# is not divisible by n
if(mp[it] >= n):
return True
# If no character has frequency
# at least N
return False
# Driver Code
str = "ccabcba"
n = 4
# Function call
if(isSame(str, n)):
print("Yes")
else:
print("No")
# This code is contributed by Shivam Singh
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to check if the freq of
// any character is divisible by N
static bool isSame(String str, int n)
{
// Stores the frequency of characters
Dictionary<int,
int> mp = new Dictionary<int,
int>();
for (int i = 0; i < str.Length; i++)
{
if(mp.ContainsKey(str[i] - 'a'))
{
mp[str[i] - 'a'] =
mp[str[i] - 'a'] + 1;
}
else
{
mp.Add(str[i] - 'a', 1);
}
}
foreach (KeyValuePair<int,
int> it in mp)
{
// If frequency of a character
// is not divisible by n
if ((it.Value) >= n)
{
return true;
}
}
// If no character has frequency
// at least N
return false;
}
// Driver Code
public static void Main(String[] args)
{
String str = "ccabcba";
int n = 4;
// Function Call
if (isSame(str, n))
{
Console.Write("Yes");
}
else
{
Console.Write("No");
}
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript program for the above approach
// Function to check if the freq of
// any character is divisible by N
function isSame(str, n)
{
// Stores the frequency of characters
var mp = {};
for(var i = 0; i < str.length; i++)
{
if (mp.hasOwnProperty(str[i].charCodeAt(0) -
"a".charCodeAt(0)))
{
mp[str[i].charCodeAt(0) - "a".charCodeAt(0)] =
mp[str[i].charCodeAt(0) - "a".charCodeAt(0)] + 1;
} else
{
mp[str[i].charCodeAt(0) -
"a".charCodeAt(0)] = 1;
}
}
for(const [key, value] of Object.entries(mp))
{
// If frequency of a character
// is not divisible by n
if (value >= n)
{
return true;
}
}
// If no character has frequency
// at least N
return false;
}
// Driver Code
var str = "ccabcba";
var n = 4;
// Function Call
if (isSame(str, n))
{
document.write("Yes");
}
else
{
document.write("No");
}
// This code is contributed by rdtank
</script>
No
Complejidad de tiempo: O(L), donde L es la longitud de la string dada
Espacio auxiliar: O(L)
Publicación traducida automáticamente
Artículo escrito por nishant0073 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA