Dadas dos strings S1 y S2 que consisten en N y M caracteres, la tarea es verificar si la string S1 puede hacerse igual a cualquier permutación de S2 después de agregar o eliminar un carácter un número primo de veces de la string S1 . Si es posible, imprima «Sí» . De lo contrario, escriba “No” .
Ejemplos:
Entrada: S1 = «gekforgk», S2 = «geeksforgeeks»
Salida: Sí
Explicación:
Si el carácter ‘e’ se agrega 3 veces (que es un número primo) y el carácter ‘s’ se agrega dos veces (que es un número primo) a S1 será «gekforgkeeess», que es una permutación de S2. Por lo tanto, imprima Sí.Entrada: S1 = “xyzzyzz”, S2 = “xyy”
Salida: No
Enfoque: el problema dado se puede resolver contando la frecuencia de los caracteres en las strings S1 y S2 y si la diferencia en cualquiera de las frecuencias de los caracteres no es primo , imprima «No» . De lo contrario, escriba «Sí» . Siga los pasos a continuación para resolver el problema:
- Inicialice la array de frecuencias, digamos freq[] de tamaño 256 .
- Itere sobre los caracteres de la string S1 y para cada carácter disminuya la frecuencia del carácter en freq[] en 1 .
- Itere sobre los caracteres de la string S2 y para cada carácter incremente la frecuencia del carácter en freq[] en 1 .
- Después de completar los pasos anteriores, si el valor absoluto de todos los elementos en freq[] son primos, imprima «Sí» . De lo contrario, escriba “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 given
// number is prime or not
bool isPrime(int n)
{
// If the number is less than 2
if (n <= 1)
return false;
// If the number is 2
else if (n == 2)
return true;
// If N is a multiple of 2
else if (n % 2 == 0)
return false;
// Otherwise, check for the
// odds values
for(int i = 3;i <= sqrt(n); i += 2)
{
if (n % i == 0)
return false;
}
return true;
}
// Function to check if S1 can be
// a permutation of S2 by adding
// or removing characters from S1
void checkPermutation(string s1, string s2)
{
// Initialize a frequency array
int freq[26] = {0};
// Decrement the frequency for
// occurrence in s1
for(char ch : s1)
{
freq[ch - 'a']--;
}
// Increment the frequency for
// occurrence in s2
for(char ch : s2)
{
freq[ch - 'a']++;
}
bool isAllChangesPrime = true;
for(int i = 0; i < 26; i++)
{
// If frequency of current
// char is same in s1 and s2
if (freq[i] == 0)
{
continue;
}
// Check the frequency for
// the current char is not
// prime
else if (!isPrime(abs(freq[i])))
{
isAllChangesPrime = false;
break;
}
}
// Print the result
if (isAllChangesPrime)
{
cout << "Yes";
}
else
{
cout << "No";
}
}
// Driver Code
int main()
{
string S1 = "gekforgk";
string S2 = "geeksforgeeks";
checkPermutation(S1, S2);
}
// This code is contributed by mohit kumar 29
Java
// Java program for the above approach
public class GFG {
// Function to check if the given
// number is prime or not
private static boolean isPrime(int n)
{
// If the number is less than 2
if (n <= 1)
return false;
// If the number is 2
else if (n == 2)
return true;
// If N is a multiple of 2
else if (n % 2 == 0)
return false;
// Otherwise, check for the
// odds values
for (int i = 3;
i <= Math.sqrt(n); i += 2) {
if (n % i == 0)
return false;
}
return true;
}
// Function to check if S1 can be
// a permutation of S2 by adding
// or removing characters from S1
private static void checkPermutation(
String s1, String s2)
{
// Initialize a frequency array
int freq[] = new int[26];
// Decrement the frequency for
// occurrence in s1
for (char ch : s1.toCharArray()) {
freq[ch - 'a']--;
}
// Increment the frequency for
// occurrence in s2
for (char ch : s2.toCharArray()) {
freq[ch - 'a']++;
}
boolean isAllChangesPrime = true;
for (int i = 0; i < 26; i++) {
// If frequency of current
// char is same in s1 and s2
if (freq[i] == 0) {
continue;
}
// Check the frequency for
// the current char is not
// prime
else if (!isPrime(
Math.abs(freq[i]))) {
isAllChangesPrime = false;
break;
}
}
// Print the result
if (isAllChangesPrime) {
System.out.println("Yes");
}
else {
System.out.println("No");
}
}
// Driver Code
public static void main(
String[] args)
{
String S1 = "gekforgk";
String S2 = "geeksforgeeks";
checkPermutation(S1, S2);
}
}
Python3
# Python 3 program for the above approach
from math import sqrt
# Function to check if the given
# number is prime or not
def isPrime(n):
# If the number is less than 2
if (n <= 1):
return False
# If the number is 2
elif(n == 2):
return True
# If N is a multiple of 2
elif(n % 2 == 0):
return False
# Otherwise, check for the
# odds values
for i in range(3,int(sqrt(n))+1,2):
if (n % i == 0):
return False
return True
# Function to check if S1 can be
# a permutation of S2 by adding
# or removing characters from S1
def checkPermutation(s1, s2):
# Initialize a frequency array
freq = [0 for i in range(26)]
# Decrement the frequency for
# occurrence in s1
for ch in s1:
if ord(ch) - 97 in freq:
freq[ord(ch) - 97] -= 1
else:
freq[ord(ch) - 97] = 1
# Increment the frequency for
# occurrence in s2
for ch in s2:
if ord(ch) - 97 in freq:
freq[ord(ch) - 97] += 1
else:
freq[ord(ch) - 97] = 1
isAllChangesPrime = True
for i in range(26):
# If frequency of current
# char is same in s1 and s2
if (freq[i] == 0):
continue
# Check the frequency for
# the current char is not
# prime
elif(isPrime(abs(freq[i]))==False):
isAllChangesPrime = False
break
# Print the result
if (isAllChangesPrime==False):
print("Yes")
else:
print("No")
# Driver Code
if __name__ == '__main__':
S1 = "gekforgk"
S2 = "geeksforgeeks"
checkPermutation(S1, S2)
# This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
using System;
class GFG{
// Function to check if the given
// number is prime or not
private static bool isPrime(int n)
{
// If the number is less than 2
if (n <= 1)
return false;
// If the number is 2
else if (n == 2)
return true;
// If N is a multiple of 2
else if (n % 2 == 0)
return false;
// Otherwise, check for the
// odds values
for(int i = 3; i <= Math.Sqrt(n); i += 2)
{
if (n % i == 0)
return false;
}
return true;
}
// Function to check if S1 can be
// a permutation of S2 by adding
// or removing characters from S1
private static void checkPermutation(
string s1, string s2)
{
// Initialize a frequency array
int[] freq = new int[26];
// Decrement the frequency for
// occurrence in s1
foreach (char ch in s1.ToCharArray())
{
freq[ch - 'a']--;
}
// Increment the frequency for
// occurrence in s2
foreach (char ch in s2.ToCharArray())
{
freq[ch - 'a']++;
}
bool isAllChangesPrime = true;
for(int i = 0; i < 26; i++)
{
// If frequency of current
// char is same in s1 and s2
if (freq[i] == 0)
{
continue;
}
// Check the frequency for
// the current char is not
// prime
else if (!isPrime(Math.Abs(freq[i])))
{
isAllChangesPrime = false;
break;
}
}
// Print the result
if (isAllChangesPrime != false)
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
// Driver Code
public static void Main(String[] args)
{
string S1 = "gekforgk";
string S2 = "geeksforgeeks";
checkPermutation(S1, S2);
}
}
// This code is contributed by target_2
Javascript
<script>
// Javascript program for the above approach
// Function to check if the given
// number is prime or not
function isPrime(n)
{
// If the number is less than 2
if (n <= 1)
return false;
// If the number is 2
else if (n == 2)
return true;
// If N is a multiple of 2
else if (n % 2 == 0)
return false;
// Otherwise, check for the
// odds values
for (let i = 3;
i <= Math.floor(Math.sqrt(n)); i += 2) {
if (n % i == 0)
return false;
}
return true;
}
// Function to check if S1 can be
// a permutation of S2 by adding
// or removing characters from S1
function checkPermutation(s1, s2)
{
// Initialize a frequency array
let freq = new Array(26);
for(let i = 0; i < 26; i++)
freq[i] = 0;
// Decrement the frequency for
// occurrence in s1
for (let ch = 0; ch < s1.length; ch++) {
freq[s1[ch].charCodeAt(0) - 'a'.charCodeAt(0)]--;
}
// Increment the frequency for
// occurrence in s2
for (let ch = 0; ch < s2.length; ch++) {
freq[s2[ch].charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
let isAllChangesPrime = true;
for (let i = 0; i < 26; i++)
{
// If frequency of current
// char is same in s1 and s2
if (freq[i] == 0) {
continue;
}
// Check the frequency for
// the current char is not
// prime
else if (!isPrime(
Math.abs(freq[i]))) {
isAllChangesPrime = false;
break;
}
}
// Print the result
if (isAllChangesPrime) {
document.write("Yes");
}
else {
document.write("No");
}
}
// Driver Code
let S1 = "gekforgk";
let S2 = "geeksforgeeks";
checkPermutation(S1, S2);
// This code is contributed by patel2127
</script>
Producción:
Yes
Complejidad de tiempo: O(max(N, M))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por abhinavjain194 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA