Compruebe si se puede obtener una permutación de S2 agregando o eliminando caracteres de S1

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:
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:

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *