Google Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
Good job dude, yeah this solution is better than mine which runs in O(nlgn). It is useful remember stuff like pigeonhole principle
@eugene.yarovoi . After reading your long post, I think your solution is similar to mine. Pls see my code and post to see if it has any problem or it is simpler.
How do you choose which character you insert next? Do you keep them sorted by frequency (like other solutions using max heap)?
@damluar The whole point is that sorting is unnecessary, so we can take the characters in any order. This is the insight that improves the solution to O (n).
@plutoman I think you have the same approach. My post goes into a little more detail as to why all the edge cases work, that's why it's slighly longer. The edge cases correspond to the two modifications you made to your code later.
I don't think you can take the put the character in any order
say "aaabc"
if you put 'a' first, you can get the right ouput 'abaca. However, you go first with 'b' or 'c', you will get the wrong output like "baaca", "cabaa" and ..
My bad, Uday is right, it doesn't work for "abccc", here you have indices 0,1,2,3,4 as you said it puts "a" at 0 , "b" at 2, c at 4, c at 1, and c at 3,
you will get "acbcc"
No it will work correctly for "abccc" see the mentioned explanation:
"If a character occurs (N+1)/2 times, all other character counts are less than N/2. The solution is to detect that character when validating the character occurrence counts, and ensure we start (at index 0) with that character"
Initial idea of zd is good, but he missed one tiny details. We actually dont need access to heap internal nodes, we can just put all characters in hashmap, and check in any character is appearing more than n/2 times we return Invalid output.
After that we put all letters in max heap, and each time we pop two items from heap. we put those two in string, decrease occurrence of each one by one, and put them again in heap if their occurrence is bigger than 0. Of course we need to check special cases if we only have one element in heap. We do this n/2 where asymptotic cost of all these operations of popping and adding to heap are 4*lgn so altogether complexity is O(nlgn).
private static String rearrangeLetters(String s) {
Map<Character, Integer> map = new HashMap<Character, Integer>();
StringBuilder res = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (!map.containsKey(c))
map.put(c, 0);
map.put(c, map.get(c) + 1);
}
PriorityQueue<Letter> PQ = new PriorityQueue<>(new Comparator<Letter>()
{
@Override
public int compare(Letter arg0, Letter arg1) {
if (arg0.occ > arg1.occ)
return -1;
else if (arg0.occ < arg1.occ)
return 1;
else
return 0;
}
});
for (Character key : map.keySet()) {
if (map.get(key) > s.length() / 2)
return "INVALID OUTPUT";
PQ.add(new Letter(map.get(key), key));
}
while(!PQ.isEmpty()) {
Letter front = PQ.poll(), secondFromFront = null;
if (!PQ.isEmpty())
secondFromFront = PQ.poll();
res.append(front.c);
if (secondFromFront != null) {
res.append(secondFromFront.c);
secondFromFront.occ--;
if (secondFromFront.occ > 0)
PQ.add(secondFromFront);
}
front.occ--;
if (front.occ > 0)
PQ.add(front);
}
return res.toString();
}
}
I have almost exact the same initial idea with @NenadCro. But I don't like the cost of pop and push top elements repeatedly out of and into the heap. Or we could do better with decrease key of node in heap if we have access to heap node.
Then I have an O(n) run time algorithm without the heap. The idea is simple, please see the code. If we have the max occurrence of characters less or equal to n/2, then we can have valid output. We just put same chars together in a string t (put max occurrence char first), and pick t[i] and t[halfLength+i] together to overwrite s. See my post below and let me know if it has problems.
I have an O(nlogn) solution.
Scan through the string and count character occurrences.
Build a max heap with the character occurrences.
Build a string with the top character.
Then loop: pull the top character and check if its the same as the previous character. If so, check the heap left or heap right to get the next highest occurrence. This means that we need to have access to the heap node internals.
we can use hashing approach here. first, we count the no of each characters.
then we start from first character to the last in the hash table.
then, we start placing each character alternatively (0, 2, 4, ...).
when it reaches the end of string then we place it like (1, 3, 5, ...).
in this way there won't be any two consecutive place with same character.
this approach will work in o(n).
^It works if you sort it by the length of characters in decreasing order. Which is more or less O(nlogn + n) ~ O(nlogn)
Can be done in O(n) time by primarily using a queue an a temp char var to keep track of the last known character. The queue will get populated every time a char is repeated and var last is used for comparison and will determine whether the current char looping through the string should be pushed to the queue or inserted to the resulting string.
string rearrange(string input) {
queue<char> q;
char last = ' ';
string result;
for (int i = 0; i < input.length(); i++) {
if(last != input[i]) {
result.insert(result.end(), input[i]);
if(!q.empty() && q.front() != result.back()) {
result.insert(result.end(), q.front());
q.pop();
}
}
else {
q.push(input[i]);
}
last = input[i];
}
return q.empty() == true ? result : NULL;
}
public class MyChar implements Comparable {
public char c;
public int count;
public MyChar(char c, int count) {
this.c = c;
this.count = count;
}
@Override
public int compareTo(Object arg0) {
// TODO Auto-generated method stub
int res = count-((MyChar)arg0).count;
if(res != 0) {
return res;
}
return ((MyChar)arg0).c-c;
}
}
public static String reorder(String s){
char[] arr = s.toCharArray();
HashMap<Character, MyChar> map = new HashMap<Character, MyChar>();
TreeSet<MyChar> set = new TreeSet<MyChar>();
for(char c:arr){
MyChar my_c = map.get(c);
if(my_c == null){
my_c = new MyChar(c,0);
map.put(c, my_c);
}
set.remove(my_c);
my_c.count++;
set.add(my_c);
}
MyChar prev = null;
for(int i =0; i<arr.length;++i){
if(set.size() == 0){
System.out.println("n"+i);
return "no solution found";
}
MyChar curr = set.last();
set.remove(curr);
curr.count--;
arr[i]=curr.c;
if(prev!=null && prev.count>0){
set.add(prev);
}
prev = curr;
}
return String.valueOf(arr);
}
public class MyChar implements Comparable {
public char c;
public int count;
public MyChar(char c, int count) {
this.c = c;
this.count = count;
}
@Override
public int compareTo(Object arg0) {
// TODO Auto-generated method stub
int res = count-((MyChar)arg0).count;
if(res != 0) {
return res;
}
return ((MyChar)arg0).c-c;
}
}
public static String reorder(String s){
char[] arr = s.toCharArray();
HashMap<Character, MyChar> map = new HashMap<Character, MyChar>();
TreeSet<MyChar> set = new TreeSet<MyChar>();
for(char c:arr){
MyChar my_c = map.get(c);
if(my_c == null){
my_c = new MyChar(c,0);
map.put(c, my_c);
}
set.remove(my_c);
my_c.count++;
set.add(my_c);
}
MyChar prev = null;
for(int i =0; i<arr.length;++i){
if(set.size() == 0){
System.out.println("n"+i);
return "no solution found";
}
MyChar curr = set.last();
set.remove(curr);
curr.count--;
arr[i]=curr.c;
if(prev!=null && prev.count>0){
set.add(prev);
}
prev = curr;
}
return String.valueOf(arr);
}
A simple solution but not efficient would be to use backtracking, this would certainly solve the problem.
#include <iostream>
using namespace std;
string TakeOutChar(string input, int i)
{
return input.substr(0, i) + input.substr(i+1, string::npos);
}
bool MakeUnique(string input, string uniqueString)
{
if(input.length() == 0)
{
cout<<"Unique string found : "<< uniqueString<< endl;
return true;
}
int uniqueStringLen = uniqueString.length();
for(int i = 0; i < input.length(); ++i)
{
if(uniqueStringLen == 0 || uniqueString[uniqueStringLen - 1] != input[i])
{
if(MakeUnique(TakeOutChar(input, i), uniqueString + input[i]))
{
return true;
}
}
}
return false;
}
int main(int nArgs, char *args[]) {
if(!MakeUnique(string(args[1]), ""))
{
cout<<"No unique strings found"<<endl;
}
return 0;
}
You may also do a simple backtracking this solution is of course not an efficient one..
#include <iostream>
using namespace std;
string TakeOutChar(string input, int i)
{
return input.substr(0, i) + input.substr(i+1, string::npos);
}
bool MakeUnique(string input, string uniqueString)
{
if(input.length() == 0)
{
cout<<"Unique string found : "<< uniqueString<< endl;
return true;
}
int uniqueStringLen = uniqueString.length();
for(int i = 0; i < input.length(); ++i)
{
if(uniqueStringLen == 0 || uniqueString[uniqueStringLen - 1] != input[i])
{
if(MakeUnique(TakeOutChar(input, i), uniqueString + input[i]))
{
return true;
}
}
}
return false;
}
int main(int nArgs, char *args[]) {
if(!MakeUnique(string(args[1]), ""))
{
cout<<"No unique strings found"<<endl;
}
return 0;
}
Suppose character occurences are x1 >= x2 >= ...>= xk
Solution will exist iff x1 - 1 <= x2 + x3 + ... + xk, that is for x1 characters we need x1 - 1 separators to achieve non-neighborhoud.
Suppose at some moment solution exists, let's prove that if we take 2 top characters, it will still exist.
x1 - 1 <= x2 + x3 + ... + xk # add x1 + 1 to both sides, n is length of string
2x1 <= n + 1
So we have
n + 1 >= 2x1 >= 2x2 >= 2x3
After we take 1 char from x1 and one from x2:
n - 1 >= 2x1 - 2 >= 2x2 - 2 >= 2x3
We have to prove that n - 1 >= 2x3
n - 1 >= x1+ x2 + x3 - 1 >= 3x3 - 1 >= 2x3, that is x3 >= 1, which is obviously true (unless we've exhausted all characters, then solution is trivial)
So we just have to take two top-frequency characters every time until there are no more characters, that is done with max-heap.
Also you should include characters themself when comparing frequencies (5, 'a') < (5, 'b') for example.
Recursive solution makes sense along with backtracking. So basically pick the character from a pool of largest character. Put it at 0th index and then recurse. In the recursion check the previous character and see if the previous character is same if same then pull the any different character and put in the current index. Recurse for the next state and do the same. Base cases is when you don't have any characters or when you have lot of same characters or same characters size is more than half the length of the string.
My approach is to first get a frequency hash for characters and then for each character place it in the first available position using greedy approach:
function getFreqOfChars(str) {
var chars = str.split("");
var result = {};
for (var i = 0; i < chars.length; i++) {
if (result[chars[i]]) {
result[chars[i]]++;
} else {
result[chars[i]] = 1;
}
}
return result;
}
function noAdjChars(str) {
var freq = getFreqOfChars(str);
var array = [];
for (var char in freq) {
array.push({char: char, freq: freq[char]});
}
array.sort(function(a, b) { return a.freq - b.freq;});
var result = new Array(str.length);
while (array.length > 0) {
var char = array.pop();
var placed = 0;
for (var i = 0; i < str.length && placed < char.freq; i++) {
if ((!result[i]) && (result[i - 1] !== char.char)) {
result[i] = char.char;
placed++;
}
}
if (placed < char.freq) {
return null;
}
}
return result.join("");
}
1. Create an array arr of alphabet size with number of occurrences of each char.
2. Sort the string.
3. Then go through string and decrement values in arr for chars you've gone through,
If two subsequent chars are equal,determine first char unequal to the current one looking at arr.
Run binary search of this char on the remainings of the string.
Complexity ~O(n * logn)
This can be done in O(n), one scan and even in place.
Assume you counter nPostponed and last postponed character.
Imagine that this is buffer of nPostponed x postponed characters.
In addition you have a last character that was copied to output.
So in each iteration you first try to take from the 'postponed' buffer if it is different from 'last'
Otherwise you take next character from source string. If it is equal to 'last' then it also must equal to postponed or postponed is empty. In this case you add it to postponed buffet - increment nPostponed
Otherwise you add this character to output and set 'last' equal to it.
At end, if postponed is not empty than task can't be done.
O(n), one scan and even in place
static boolean rearrange(char[] ar) {
if (ar.length < 2) return true;
int s = 0; // source;
char last = ar[s++];
int t = 1; // destination - first char already there
char postponed = '?'; // buffer is empty it this value is ignored
int nPostponed = 0;
while (s < ar.length || nPostponed > 0) {
// is character in postponed buffer ?
if (nPostponed > 0 && postponed != last) {
// Remove from postponed buffer
ar[t++] = postponed;
--nPostponed;
last = postponed;
} else {
if ( ! (s < ar.length) ) {
// no more to take from
return false;
}
char c = ar[s++];
if (c != last) {
ar[t++] = c;
last = c;
} else {
// so it must equals postponed if the later is not empty
// Add to postponed buffer
++nPostponed;
postponed = c;
}
}
}
return true;
}
I have almost exact the same initial idea with @NenadCro. But I don't like the cost of pop and push top elements repeatedly out of and into the heap. Or we could do better with decrease key of node in heap if we have access to heap node.
Then I have an O(n) run time algorithm without the heap. The idea is simple, please see the code. If we have the max occurrence of characters less or equal to n/2, then we can have valid output. We just put same chars together in a string t, and pick t[i] and t[halfLength+i] together to overwrite s.
class Solver{
public:
bool rearrageString(string& s){
if(s.empty()) return true;
vector<int> charNums(52, 0);
int maxNums=0;
int n=s.size();
for(int i=0; i<n; i++){
charNums[ s[i]-'a' ]++;
maxNums = max(maxNums, charNums[ s[i]-'a' ]);
}
if(maxNums>n/2) return false;
string t;
int count=0;
for(int i=0; i<n; i++){
if(charNums[ s[i]-'a' ]>0){
t.append(charNums[ s[i]-'a' ], s[i]);
count +=charNums[ s[i]-'a' ];
charNums[ s[i]-'a' ] =0;
if(count==n) break;
}
}
int halfCount= n/2;
for(int i=0; i<halfCount; i++){
s[i*2]= t[i];
s[i*2+1]= t[halfCount+i];
}
if(n%2!=0) s[n-1]=t[halfCount];
return true;
}
};
made two changes to code above, use ceiling (n+1)/2 instead of n/2. Add max occurrence char first to t. See modified code below.
class Solver{
public:
bool rearrageString(string& s){
if(s.empty()) return true;
vector<int> charNums(52, 0);
int maxNums=0, maxIdx=0;
int n=s.size();
for(int i=0; i<n; i++){
charNums[ s[i]-'a' ]++;
if(maxNums<charNums[ s[i]-'a' ]){
maxNums = charNums[ s[i]-'a' ];
maxIdx = i;
}
}
if(maxNums>(n+1)/2) return false;
string t;
int count=0;
//append the max occurrence char first
t.append(maxNums, s[maxIdx]);
count +=maxNums;
charNums[ s[maxIdx]-'a' ] =0;
for(int i=0; i<n; i++){
if(charNums[ s[i]-'a' ]>0){
t.append(charNums[ s[i]-'a' ], s[i]);
count +=charNums[ s[i]-'a' ];
charNums[ s[i]-'a' ] =0;
if(count==n) break;
}
}
int halfCount= (n+1)/2;
for(int i=0; i<halfCount; i++){
s[i*2]= t[i];
s[i*2+1]= t[halfCount+i];
}
if(n%2!=0) s[n-1]=t[halfCount];
return true;
}
};
c++, greedy
#include <map>
string rearrange(string str) {
string result, last, temp;
map<string, int> counts;
map<string, int>::iterator it;
multimap<int, string> remains;
multimap<int, string>::reverse_iterator rit;
int i;
for (i = 0; i < str.size(); i++) {
temp = str.substr(i, 1);
it = counts.find(temp);
if (it != counts.end()) {
it->second++;
} else {
counts.insert(make_pair(temp, 1));
}
}
for (it = counts.begin(); it != counts.end(); it++) {
remains.insert(make_pair(it->second, it->first));
}
counts.clear();
result = "";
if (remains.size() > 0) {
rit = remains.rbegin();
if (rit->first * 2 - 2 >= str.size()) return "No valid output";
last = "";
while (remains.size()) {
rit = remains.rbegin();
if (last.compare(rit->second) == 0) rit++;
i = rit->first;
last = rit->second;
remains.erase(next(rit).base());
result.append(last);
if (i > 1) remains.insert(make_pair(i - 1, last));
}
}
return result;
}
I have a simple solution that's O(n*log(n)) and doesn't require any character counting.
-Sort the array ( O(n*log(n) )
-Traverse the array and make sure no letter appears more than (n/2) times ( O(n) )
-shift elements in odd positions (1,3,5,..) the array by (n/2+1) if n is even or by (n+1)/2 if n is odd.
-you are done :)
-Sort the array O(n*log(n))
-Traverse the array and make sure no letter appears more than (n/2) times O(n)
-Shift the items in the odd positions (1,3,5,..) by (n/2+1) if n is even and by (n+1)/2 if n is odd O(n)
-you are done :)
Proof of correctness:
consider any block of letters starting at position x and ending at position y;
1- Since every other element of this block is replaced by a letter of another block, there would be no duplicates in this block.
2- Elements removed from this block will be moved another blocks and they would not be adjacent
-Sort the array O(n*log(n))
-Traverse the array and make sure no letter appears more than (n/2) times O(n)
-Shift the items in the odd positions (1,3,5,..) by (n/2+1) if n is even and by (n+1)/2 if n is odd O(n)
-you are done :)
Proof of correctness:
consider any block of letters starting at position x and ending at position y;
1- Since every other element of this block is replaced by a letter of another block, there would be no duplicates in this block.
2- Elements removed from this block will be moved another blocks and they would not be adjacent
Time complexity O(L) where L is the string length; space O(L)
public static char[] reorder(String s){
if(s==null || s.length()==0 || (s.length()==2 && s.charAt(0)==s.charAt(1)))
return "No valid Output.".toCharArray();
boolean problem=false;
int i=0,j=s.length() -1;
char [] temp= s.toCharArray();
while((i+ 1 ) < j){
if(temp[i] == temp[i+1]){
if(temp[i] == temp[j] || (j+1 <temp.length && temp[i]==temp[j+1] ))
problem=true;
else{
temp[i+1]=temp[j];
temp[j]=temp[i];
problem=false;
i++;
}
j--;
}
else
i++;
}
if(problem)
return "No valid Output.".toCharArray();
return temp;
}
private String noRepeatingChars(String input) {
Map<Character, Integer> histogram = new LinkedHashMap<Character, Integer>();
char[] chars = input.toCharArray();
for (int i = 0; i < chars.length; i++) {
char c = chars[i];
if (histogram.contains(c)) {
histogram.put(c, histogram.get(c) + 1);
} else {
histogram.put(c, 1);
}
}
String output = “”;
Character prevChar = null;
while (!histogram.isEmpty()) {
Iterator<Map.Entry<Character, Integer>> iterator;
for (iterator = histogram.iterator(); iterator.hasNext() ;) {
Map.Entry<Character, Integer> entry = iterator.next();
if (entry.key == prevChar) return “INVALID”;
prevChar = entry.key;
output = output + prevChar;
entry.value—;
if (entry.value == 0) iterator.remove();
}
}
return output;
}
This code does not compile. But if assuming this code
private static String noRepeatingChars(String input) {
Map<Character, Integer> histogram = new LinkedHashMap<Character, Integer>();
char[] chars = input.toCharArray();
for (int i = 0; i < chars.length; i++) {
char c = chars[i];
if (histogram.containsKey(c)) {
histogram.put(c, histogram.get(c) + 1);
} else {
histogram.put(c, 1);
}
}
String output = "";
Character prevChar = null;
while (!histogram.isEmpty()) {
Iterator<Map.Entry<Character, Integer>> iterator;
for (iterator = histogram.entrySet().iterator(); iterator.hasNext() ;) {
Map.Entry<Character, Integer> entry = iterator.next();
if (entry.getKey() == prevChar) return "INVALID";
prevChar = entry.getKey();
output = output + prevChar;
entry.setValue(entry.getValue() - 1);
if (entry.getValue() == 0) iterator.remove();
}
}
return output;
}
=========================
Then it fails for "aabbb".
1) take two array of size 256 each and initialize the frequency of every character and sort it with respect to frequency of characters ,sorting of array of 256 take O(1) scanning of string take O(n)
2)if max freq is greater than n/2 return invalid
3)print every character to the number of times the frequency of Lowest_frequency_character, update the freq of characters in array by substracting with the frequency of lowest_freq_character
4)We have printed all the lowest freq character and every other characters with the same number of time
5)printing order will be from high to low freq character like abcd abc ab a
6)Repeat the same process for the second lowest freq and so on
so total running time => O(n)
1) take two array of size 256 each and initialize the frequency of every character and sort it with respect to frequency of characters ,sorting of array of 256 take O(1) scanning of string take O(n)
2)if max freq is greater than n/2 return invalid
3)print every character to the number of times the frequency of Lowest_frequency_character, update the freq of characters in array by substracting with the frequency of lowest_freq_character
4)We have printed all the lowest freq character and every other characters with the same number of time
5)printing order will be from high to low freq character like abcd abc ab a
6)Repeat the same process for the second lowest freq and so on
so total running time => O(n)
1) take two array of size 256 each and initialize the frequency of every character and sort it with respect to frequency of characters ,sorting of array of 256 take O(1) scanning of string take O(n)
2)if max freq is greater than n/2 return invalid
3)print every character to the number of times the frequency of Lowest_frequency_character, update the freq of characters in array by substracting with the frequency of lowest_freq_character
4)We have printed all the lowest freq character and every other characters with the same number of time
5)printing order will be from high to low freq character like abcd abc ab a
6)Repeat the same process for the second lowest freq and so on
so total running time => O(n)
1) take two array of size 256 each and initialize the frequency of every character and sort it with respect to frequency of characters ,sorting of array of 256 take O(1) scanning of string take O(n)
2)if max freq is greater than n/2 return invalid
3)print every character to the number of times the frequency of Lowest_frequency_character, update the freq of characters in array by substracting with the frequency of lowest_freq_character
4)We have printed all the lowest freq character and every other characters with the same number of time
5)printing order will be from high to low freq character like abcd abc ab a
6)Repeat the same process for the second lowest freq and so on
so total running time => O(n)
1) take two array of size 256 each and initialize the frequency of every character and sort it with respect to frequency of characters ,sorting of array of 256 take O(1) scanning of string take O(n)
2)if max freq is greater than n/2 return invalid
3)print every character to the number of times the frequency of Lowest_frequency_character, update the freq of characters in array by substracting with the frequency of lowest_freq_character
4)We have printed all the lowest freq character and every other characters with the same number of time
5)printing order will be from high to low freq character like abcd abc ab a
6)Repeat the same process for the second lowest freq and so on
so total running time => O(n)
1) take two array of size 256 each and initialize the frequency of every character and sort it with respect to frequency of characters ,sorting of array of 256 take O(1) scanning of string take O(n)
2)if max freq is greater than n/2 return invalid
3)print every character to the number of times the frequency of Lowest_frequency_character, update the freq of characters in array by substracting with the frequency of lowest_freq_character
4)We have printed all the lowest freq character and every other characters with the same number of time
5)printing order will be from high to low freq character like abcd abc ab a
6)Repeat the same process for the second lowest freq and so on
so total running time => O(n)
Here is a shorter one in scala...
def rearrange(input: String): String = {
val list = input.groupBy { x => x }.values.flatten
val k = input.groupBy { x => x }.mapValues { x => x.size }
if (k.values.max > Math.ceil(input.length() / 2.0))
"NA"
else {
val part = k.toSeq.sortWith(_._2 > _._2)
.flatMap { elem => List.fill(elem._2)(elem._1) }
val (x, y) = if (s.length() % 2 == 0) part.splitAt(list.size / 2)
else part.splitAt(list.size / 2 + 1)
val p = ((x zip y).flatMap { x => List(x._1, x._2) }).mkString
if(x.size > y.size)
p + x.head
else p
}
}
I don't get why all the nlogn answers are voted up, this is a very simple O(n) problem. Simply iterate from left and when you encounter two consecutive characters, send another iterator to search for the next character which isnt the two characters encountered, and replace the second one with that. Then do this from right to left. C++ code:
string noRepeats(string s) {
// assume len at least 2
int idx = 1;
int end = 2;
for (; idx < s.size(); idx++) {
if (s[idx] == s[idx - 1]) {
end = max(end, idx + 1);
while (end < s.size() && s[end] == s[idx]) end++;
if (end == s.size()) break;
swap(s[idx], s[end]);
}
}
for (idx = s.size() - 1; idx >= 0; idx--) {
if (s[idx] == s[idx + 1]) {
end = min(end, idx - 1);
while (end >= 0 && s[end] == s[idx]) end--;
if (end == -1) break;
swap(s[idx], s[end]);
}
}
for (int i = 1; i < s.size(); i++) {
if (s[i] == s[i - 1]) {
return "";
}
}
return s;
}
using char_count_t = pair<int, char>;
using char_count_queue_t = priority_queue<char_count_t,
vector<char_count_t>, std::greater<char_count_t>>;
string rearange(string&& input) {
sort(input.begin(), input.end());
map<char, int> count;
for (char c : input)
count[c]++;
char_count_queue_t queue;
for (auto &counted_char : count) {
queue.push(counted_char);
}
string result;
auto prev = make_pair('\0', 0);
while (!queue.empty()) {
auto counted_char = queue.top(); queue.pop();
counted_char.second--;
if (prev.second)
queue.push(prev);
prev = counted_char;
result.push_back(counted_char.first);
}
if (prev.second)
return string("no valid output");
return result;
}
Run time: O(n)
Assumptions:
1) Input is sorted
Python:
def no_repeat(inp, flip_side=False):
i = 0
while i < len(inp) - 1:
if inp[i] == inp[i+1]:
if inp[i] == inp[-1]:
if flip_side:
return False
else:
rev_inp = list(inp)
rev_inp.reverse()
return no_repeat("".join(rev_inp), True)
else:
inp = inp[:i+1] + inp[-1] + inp[i+1:-1]
i+=1
return inp
Solution:
string=input()
def recognization(string):
characters=dict()
i=0
for i in range(len(string)):
if string[i] not in characters:
characters[string[i]]=1
else:
characters[string[i]]+=1
return characters
mascharacter=recognization(string)
masch=[]
for i,j in mascharacter.items():
masch.append([j,i])
print(masch)
def canwerearrange(characters):
mas=[]
answer=""
for i in characters.values():
mas.append(int(i))
mas=sorted(mas)
s=0
for i in range(len(mas)-1):
s+=mas[i]
if mas[len(mas)-1]-s>1:
answer+="no"
else:
answer+="yes"
return answer
def sort(ch):
mas=[]
mas1=[]
for j in range(len(ch)-1):
for i in range(len(ch)-1):
if ch[i][0]<ch[i+1][0]:
mas.append(ch[i+1][0])
ch[i+1][0]=ch[i][0]
ch[i][0]=mas[0]
mas1.append(ch[i+1][1])
ch[i+1][1]=ch[i][1]
ch[i][1]=mas1[0]
mas=[]
mas1=[]
return ch
def rearrange(string,answer,ch):
rearstring=""
s=0
i=0
if answer!="no":
for i in range(len(string)):
if i>0 and ch[s][1]!=rearstring[i-1]:
if ch[s][0]>0:
rearstring+=ch[s][1]
ch[s][0]-=1
ch=sort(ch)
elif i==0:
if ch[s][0]>0:
rearstring+=ch[s][1]
ch[s][0]-=1
ch=sort(ch)
elif i>0 and ch[s][1]==rearstring[i-1]:
s+=1
if ch[s][0]>0 :
rearstring+=ch[s][1]
ch[s][0]-=1
s-=1
ch=sort(ch)
else:
print("No valid output")
return(rearstring)
print(rearrange(string,canwerearrange(recognization(string)),sort(masch)))
input:
aaaaaaabbbbccc
output
ababacacababac
Here is C++ version of solution running in O(n logN).
using heap to keep the node with max value.
#include<cstdint>
#include <string>
#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;
struct node {
char value;
int count;
node(char v, int c):value(v), count(c){}
};
bool larger(char prev, char next)
{
return prev < next;
}
string find_norepeat_str(vector<char>& input)
{
string result;
vector<node*> nodes;
sort(input.begin(), input.end(), larger);
char cur = INT8_MIN;
int left = input.size();
int count = 0;
for(int i = 0; i < input.size(); i++)
{
if (cur == INT8_MIN)
{
cur = input[i];
count++;
} else if (cur == input[i])
{
count++;
} else {
nodes.push_back(new node(cur, count));
cur = input[i];
count = 1;
}
}
nodes.push_back(new node(cur, count));
Heap heap(nodes);
node * longest = 0;
while (left>0)
{
if (!longest || longest->count == 0)
{
longest = heap.extract();
}
while (longest && longest->count>0)
{
node * next = heap.extract();
if (!next)
{
if (longest->count == 1)
{
result.push_back(longest->value);
return result;
}else
return "invalid input";
}
if(result.length()==0 || (result.length() > 0 && result[result.length()-1] != longest->value))
{
result.push_back(longest->value);
longest->count--;
left--;
}
result.push_back(next->value);
next->count--;
left --;
if (next->count)
heap.add(next);
}
}
return result;
}
Here is an approach that runs in O(n) time.
- eugene.yarovoi October 10, 2015To clarify the idea, we will first assume that every character occurs in the string less than N/2 times, where N is the length of the string. This is not a perfect assumption, because the string may still be valid if there's one letter that occurs N/2 or (N+1)/2 times. e.g. abaca is a valid arrangement. After discussing the general approach, we can take care of this special case.
First, we count the number of occurrences of each character using an array or hash table, depending on whether the size of the alphabet is small or large. After that, we place occurrences of the first character at indices 0, 2, 4, 6, ..., etc., so that occurrences of the character are never together. If the first character used indices 0, 2, ..., 20, the second character would be placed at 22, 24, 26, etc. Upon reaching the end of the array, we would wrap around and start filling odd indices, like 1, 3, 5, in that order
To be precise, we keep a numCharsPlaced variable. If we've already written a total of numCharsPlaced characters (counting repeated chars), the next character is to be placed at (2*numCharsPlaced)%arr.length+adjustment, where adjustment is 1 if the array size is even, 0 if it's odd.
Note that this algorithm never places two identical characters next to each other, except when a character's count is so high that the wraparound to odd indices occurs and we get all the way back to where the even-indexed occurrences of the character occurred. This can only happen if a character occurs at least N/2 times.
If a character occurs (N+1)/2 times, all other character counts are less than N/2. The solution is to detect that character when validating the character occurrence counts, and ensure we start (at index 0) with that character (this will give this character enough space, and all other characters have enough space by the general proof given before). If a character occurs exactly N/2 times, we use the same remedy as for the (N+1)/2 case. In the N/2 case, it's possible that there is one other character that also occurs N/2 times, but we verify that the algorithm behaves correctly in this case.
If a character occurs more than (N+1)/2 times, there is no solution. That's because you can split the input into that many pairs of adjacent locations, and you can argue by pigeonhole principle that at least one such pair of locations must have more than one of the same character, which would mean that the same character occurs twice consecutively.