Rearrange the given string such that all prime multiple indexes have same character
Given a string str of size N. The task is to find out whether it is possible to rearrange characters in string str so that for any prime number p <= N and for any integer i ranging from 1 to N/p the condition strp = strp*i must be satisfied. If it is not possible to for any such rearrangement then print -1. Examples:
Input : str = “aabaaaa” Output : baaaaaa Size of the string is 7. Indexes 2, 4, 6 contains same character. Indexes 3, 6 contains the same character. Input : str = “abcd” Output : -1
Approach:
- All positions except the first and those whose number is a prime greater N/2 must have the same symbol.
- Remaining positions can have any symbol. This positions kept using the sieve.
- If the most occurred element in the string is less than these positions then print -1.
Below is the implementation of the above approach:
C++
// CPP program to rearrange the given // string such that all prime multiple // indexes have same character #include <bits/stdc++.h> using namespace std; #define N 100005 // To store answer char ans[N]; int sieve[N]; // Function to rearrange the given string // such that all prime multiple indexes // have the same character. void Rearrange(string s, int n) { // 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 fill(sieve + 1, sieve + n + 1, 1); // To store number of positions required // to store elements of same kind int sz = 0; // Start sieve for ( int i = 2; i <= n / 2; i++) { if (sieve[i]) { // For all multiples of i for ( int j = 1; i * j <= n; j++) { if (sieve[i * j]) sz++; sieve[i * j] = 0; } } } // map to store frequency of each character map< char , int > m; for ( auto it : s) m[it]++; // Store all characters in the vector and // sort the vector to find the character with // highest frequency vector<pair< int , char > > v; for ( auto it : m) v.push_back({ it.second, it.first }); sort(v.begin(), v.end()); // If most occurred character is less than // required positions if (v.back().first < sz) { cout << -1; return ; } // In all required positions keep // character which occurred most times for ( int i = 2; i <= n; i++) { if (!sieve[i]) { ans[i] = v.back().second; } } // Fill all other indexes with // remaining characters int idx = 0; for ( int i = 1; i <= n; i++) { if (sieve[i]) { ans[i] = v[idx].second; v[idx].first--; // If character frequency becomes // zero then go to next character if (v[idx].first == 0) idx++; } cout << ans[i]; } } // Driver code int main() { string str = "aabaaaa" ; int n = str.size(); // Function call Rearrange(str, n); return 0; } |
Java
import java.util.*; public class RearrangeString { static final int N = 100005 ; static char [] ans = new char [N]; static int [] sieve = new int [N]; // Function to rearrange the given string // such that all prime multiple indexes // have the same character. static void Rearrange(String s, int n) { // Initially assume that we can keep // any symbol at any positions. // If at any index contains one then it is not // counted in our required positions Arrays.fill(sieve, 1 ); // To store number of positions required // to store elements of the same kind int sz = 0 ; // Start sieve for ( int i = 2 ; i <= n / 2 ; i++) { if (sieve[i] == 1 ) { // For all multiples of i for ( int j = 1 ; i * j <= n; j++) { if (sieve[i * j] == 1 ) sz++; sieve[i * j] = 0 ; } } } // map to store frequency of each character Map<Character, Integer> m = new HashMap<>(); for ( char c : s.toCharArray()) m.put(c, m.getOrDefault(c, 0 ) + 1 ); // Store all characters in the vector and // sort the vector to find the character with // the highest frequency Vector<Pair> v = new Vector<>(); for (Map.Entry<Character, Integer> entry : m.entrySet()) v.add( new Pair(entry.getValue(), entry.getKey())); v.sort((a, b) -> Integer.compare(a.first, b.first)); // If the most occurred character is less than // required positions if (v.lastElement().first < sz) { System.out.println(- 1 ); return ; } // In all required positions keep // a character that occurred the most times for ( int i = 2 ; i <= n; i++) { if (sieve[i] == 0 ) { ans[i] = v.lastElement().second; } } // Fill all other indexes with // remaining characters int idx = 0 ; for ( int i = 1 ; i <= n; i++) { if (sieve[i] == 1 ) { ans[i] = v.get(idx).second; v.get(idx).first--; // If character frequency becomes // zero then go to the next character if (v.get(idx).first == 0 ) idx++; } System.out.print(ans[i]); } } // Driver code public static void main(String[] args) { String str = "aabaaaa" ; int n = str.length(); // Function call Rearrange(str, n); } static class Pair { int first; char second; Pair( int first, char second) { this .first = first; this .second = second; } } } |
Python3
# Python3 program to rearrange the given # string such that all prime multiple # indexes have same character N = 100005 # To store answer ans = [ 0 ] * N; # sieve = [1]*N; # Function to rearrange the given string # such that all prime multiple indexes # have the same character. def Rearrange(s, n) : # 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 sieve = [ 1 ] * (N + 1 ); # To store number of positions required # to store elements of same kind sz = 0 ; # Start sieve for i in range ( 2 , n / / 2 + 1 ) : if (sieve[i]) : # For all multiples of i for j in range ( 1 , n / / i + 1 ) : if (sieve[i * j]) : sz + = 1 ; sieve[i * j] = 0 ; # map to store frequency of each character m = dict .fromkeys(s, 0 ); for it in s : m[it] + = 1 ; # Store all characters in the vector and # sort the vector to find the character with # highest frequency v = []; for key,value in m.items() : v.append([ value, key] ); v.sort(); # If most occurred character is less than # required positions if (v[ - 1 ][ 0 ] < sz) : print ( - 1 ,end = ""); return ; # In all required positions keep # character which occurred most times for i in range ( 2 , n + 1 ) : if ( not sieve[i]) : ans[i] = v[ - 1 ][ 1 ]; # Fill all other indexes with # remaining characters idx = 0 ; for i in range ( 1 , n + 1 ) : if (sieve[i]): ans[i] = v[idx][ 1 ]; v[idx][ 0 ] - = 1 ; # If character frequency becomes # zero then go to next character if (v[idx][ 0 ] = = 0 ) : idx + = 1 ; print (ans[i],end = ""); # Driver code if __name__ = = "__main__" : string = "aabaaaa" ; n = len (string); # Function call Rearrange(string, n); # This code is contributed by AnkitRai01 |
C#
using System; using System.Collections.Generic; using System.Linq; class Program { const int N = 100005; // To store answer static char [] ans = new char [N]; static int [] sieve = new int [N]; // Function to rearrange the given string // such that all prime multiple indexes // have the same character. static void Rearrange( string s, int n) { // Initially assume that we can keep // any symbol at any positions. // If at any index contains one then it is not // counted in our required positions Array.Fill(sieve, 1, 1, n); // To store the number of positions required // to store elements of the same kind int sz = 0; // Start sieve for ( int i = 2; i <= n / 2; i++) { if (sieve[i] == 1) { // For all multiples of i for ( int j = 1; i * j <= n; j++) { if (sieve[i * j] == 1) sz++; sieve[i * j] = 0; } } } // Dictionary to store the frequency of each character Dictionary< char , int > m = new Dictionary< char , int >(); foreach ( char c in s) { if (m.ContainsKey(c)) m++; else m = 1; } // Store all characters in the list and // sort the list to find the character with // the highest frequency List<Tuple< int , char >> v = new List<Tuple< int , char >>(); foreach ( var kvp in m) { v.Add( new Tuple< int , char >(kvp.Value, kvp.Key)); } v = v.OrderBy(t => t.Item1).ToList(); // If the most occurred character is less than // required positions if (v.Last().Item1 < sz) { Console.WriteLine(-1); return ; } // In all required positions keep // the character which occurred most times for ( int i = 2; i <= n; i++) { if (sieve[i] == 0) { ans[i] = v.Last().Item2; } } // Fill all other indexes with // remaining characters int idx = 0; for ( int i = 1; i <= n; i++) { if (sieve[i] == 1) { ans[i] = v[idx].Item2; v[idx] = new Tuple< int , char >(v[idx].Item1 - 1, v[idx].Item2); // If character frequency becomes // zero then go to the next character if (v[idx].Item1 == 0) idx++; } Console.Write(ans[i]); } } // Driver code static void Main() { string str = "aabaaaa" ; int n = str.Length; // Function call Rearrange(str, n); } } |
Javascript
// Javascript program for the above approach const N = 100005; const ans = new Array(N).fill(0); function Rearrange(s, n) { const sieve = new Array(N + 1).fill(1); let sz = 0; for (let i = 2; i <= Math.floor(n / 2); i++) { if (sieve[i]) { for (let j = 1; j <= Math.floor(n / i); j++) { if (sieve[i * j]) { sz += 1; } sieve[i * j] = 0; } } } const m = {}; for (const c of s) { m = (m || 0) + 1; } const v = []; for (const [key, value] of Object.entries(m)) { v.push([value, key]); } v.sort(); if (v[v.length - 1][0] < sz) { console.log(-1); return ; } for (let i = 2; i <= n; i++) { if (!sieve[i]) { ans[i] = v[v.length - 1][1]; } } let idx = 0; for (let i = 1; i <= n; i++) { if (sieve[i]) { ans[i] = v[idx][1]; v[idx][0] -= 1; if (v[idx][0] === 0) { idx += 1; } } process.stdout.write(ans[i] || '' ); } } const string = 'aabaaaa' ; const n = string.length; Rearrange(string, n); // contributed by adityasharmadev01 |
Output
baaaaaa