Rearrange the given string such that all prime multiple indexes have same character | Python3 program to rearrange the given string such that all prime multiple indexes have same character ; To store answer ; Function to rearrange the given string such that all prime multiple indexes have the same character . ; Initially assume that we can kept any symbol at any positions . If at any index contains one then it is not counted in our required positions ; To store number of positions required to store elements of same kind ; Start sieve ; For all multiples of i ; map to store frequency of each character ; Store all characters in the vector and sort the vector to find the character with highest frequency ; If most occured character is less than required positions ; In all required positions keep character which occured most times ; Fill all other indexes with remaining characters ; If character frequency becomes zero then go to next character ; Driver code ; Function call
N = 100005 NEW_LINE ans = [ 0 ] * N ; NEW_LINE def Rearrange ( s , n ) : NEW_LINE INDENT sieve = [ 1 ] * ( N + 1 ) ; NEW_LINE sz = 0 ; NEW_LINE for i in range ( 2 , n // 2 + 1 ) : NEW_LINE INDENT if ( sieve [ i ] ) : NEW_LINE INDENT for j in range ( 1 , n // i + 1 ) : NEW_LINE INDENT if ( sieve [ i * j ] ) : NEW_LINE INDENT sz += 1 ; NEW_LINE DEDENT sieve [ i * j ] = 0 ; NEW_LINE DEDENT DEDENT DEDENT m = dict . fromkeys ( s , 0 ) ; NEW_LINE for it in s : NEW_LINE INDENT m [ it ] += 1 ; NEW_LINE DEDENT v = [ ] ; NEW_LINE for key , value in m . items ( ) : NEW_LINE INDENT v . append ( [ value , key ] ) ; NEW_LINE DEDENT v . sort ( ) ; NEW_LINE if ( v [ - 1 ] [ 0 ] < sz ) : NEW_LINE INDENT print ( - 1 , end = " " ) ; NEW_LINE return ; NEW_LINE DEDENT for i in range ( 2 , n + 1 ) : NEW_LINE INDENT if ( not sieve [ i ] ) : NEW_LINE INDENT ans [ i ] = v [ - 1 ] [ 1 ] ; NEW_LINE DEDENT DEDENT idx = 0 ; NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT if ( sieve [ i ] ) : NEW_LINE INDENT ans [ i ] = v [ idx ] [ 1 ] ; NEW_LINE v [ idx ] [ 0 ] -= 1 ; NEW_LINE if ( v [ idx ] [ 0 ] == 0 ) : NEW_LINE INDENT idx += 1 ; NEW_LINE DEDENT DEDENT print ( ans [ i ] , end = " " ) ; NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT string = " aabaaaa " ; NEW_LINE n = len ( string ) ; NEW_LINE Rearrange ( string , n ) ; NEW_LINE DEDENT