Given two strings S1 and S2 consisting of N and M characters, the task is to check if the string S1 can be made equal to any permutation of S2 after adding or removing a character a prime number of times from the string S1. If it is possible then print “Yes”. Otherwise, print “No”.
Examples:
Input: S1 = “gekforgk”, S2 = “neveropen”
Output: Yes
Explanation:
If character ‘e’ is added 3(which is a prime number) times and character ‘s’ is added two(which is a prime number) times to S1 it will be “gekforgkeeess” which is a permutation of S2. Therefore, print Yes.Input: S1 = “xyzzyzz”, S2 = “xyy”
Output: No
Approach: The given problem can be solved by counting the frequency of characters in strings S1 and S2 and if the difference in any of the frequency of the characters is not prime then print “No”. Otherwise, print “Yes”. Follow the steps below to solve the problem:
- Initialize the frequency array, say freq[] of size 256.
- Iterate over the characters of string S1 and for every character decrement the frequency of character in freq[] by 1.
- Iterate over the characters of string S2 and for every character increment the frequency of character in freq[] by 1.
- After completing the above steps, if the absolute value of all the elements in freq[] are prime, then print “Yes”. Otherwise, print “No”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if the given// number is prime or notbool 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 S1void 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 Codeint main(){ string S1 = "gekforgk"; string S2 = "neveropen"; checkPermutation(S1, S2);}// This code is contributed by mohit kumar 29 |
Java
// Java program for the above approachpublic 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 = "neveropen"; checkPermutation(S1, S2); }} |
Python3
# Python 3 program for the above approachfrom math import sqrt# Function to check if the given# number is prime or notdef 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 S1def 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 Codeif __name__ == '__main__': S1 = "gekforgk" S2 = "neveropen" checkPermutation(S1, S2) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approachusing System;class GFG{// Function to check if the given// number is prime or notprivate 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 S1private 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 Codepublic static void Main(String[] args){ string S1 = "gekforgk"; string S2 = "neveropen"; 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 notfunction 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 S1function 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 Codelet S1 = "gekforgk";let S2 = "neveropen";checkPermutation(S1, S2);// This code is contributed by patel2127</script> |
Output:
Yes
Time Complexity: O(max(N, M))
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
