Check if a permutation of S2 can be obtained by adding or removing characters from S1 | Python 3 program for the above approach ; Function to check if the given number is prime or not ; If the number is less than 2 ; If the number is 2 ; If N is a multiple of 2 ; Otherwise , check for the odds values ; Function to check if S1 can be a permutation of S2 by adding or removing characters from S1 ; Initialize a frequency array ; Decrement the frequency for occurrence in s1 ; Increment the frequency for occurence in s2 ; If frequency of current char is same in s1 and s2 ; Check the frequency for the current char is not prime ; Print the result ; Driver Code
from math import sqrt NEW_LINE def isPrime ( n ) : NEW_LINE INDENT if ( n <= 1 ) : NEW_LINE INDENT return False NEW_LINE DEDENT elif ( n == 2 ) : NEW_LINE INDENT return True NEW_LINE DEDENT elif ( n % 2 == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT for i in range ( 3 , int ( sqrt ( n ) ) + 1 , 2 ) : NEW_LINE INDENT if ( n % i == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT return True NEW_LINE DEDENT def checkPermutation ( s1 , s2 ) : NEW_LINE INDENT freq = [ 0 for i in range ( 26 ) ] NEW_LINE for ch in s1 : NEW_LINE INDENT if ord ( ch ) - 97 in freq : NEW_LINE INDENT freq [ ord ( ch ) - 97 ] -= 1 NEW_LINE DEDENT else : NEW_LINE INDENT freq [ ord ( ch ) - 97 ] = 1 NEW_LINE DEDENT DEDENT for ch in s2 : NEW_LINE INDENT if ord ( ch ) - 97 in freq : NEW_LINE INDENT freq [ ord ( ch ) - 97 ] += 1 NEW_LINE DEDENT else : NEW_LINE INDENT freq [ ord ( ch ) - 97 ] = 1 NEW_LINE DEDENT DEDENT isAllChangesPrime = True NEW_LINE for i in range ( 26 ) : NEW_LINE INDENT if ( freq [ i ] == 0 ) : NEW_LINE INDENT continue NEW_LINE DEDENT elif ( isPrime ( abs ( freq [ i ] ) ) == False ) : NEW_LINE INDENT isAllChangesPrime = False NEW_LINE break NEW_LINE DEDENT DEDENT if ( isAllChangesPrime == False ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT S1 = " gekforgk " NEW_LINE S2 = " geeksforgeeks " NEW_LINE checkPermutation ( S1 , S2 ) NEW_LINE DEDENT