plutoman
BAN USERI 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.
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;
}
};
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;
}
};
@MehrdadAP , nice solution. I came up with the similar solution as your second one. However, I would like to point out that the use of master theorem for run time analyze of the first solution is wrong. Actually master theorem doesn't apply for this case as nlogn is not polynomially larger than n=n^(log2(2)). Therefore, I doubt what its real run time is.
- plutoman October 01, 2015
@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.
- plutoman October 13, 2015