Here's my O(n) solution in C++:

#include <string>
#include <vector>
#include <algorithm>
#include <cassert>
#include <iostream>
using namespace std;
class Solution {
public:
Solution() : size(0), pos(0) {}
typedef pair<char, int> CharCount;
vector<CharCount> count;
int size; // how many chars in count to be output
int pos; // pointer to count
//Count frequency of chars, setting members count and size.
void count_char(const string & s) {
vector<int> frequency(26);
for (int i = 0; i < s.size(); i++) {
int idx = s[i] - 'A';
assert(idx >= 0 && idx < frequency.size());
frequency[idx]++;
}
for (int i = 0; i < frequency.size(); i++) {
if (frequency[i] > 0) {
count.push_back(make_pair('A' + i, frequency[i]));
}
}
//Sort elements with bigger count before less one, so that they'll be output
//in that order. See next_char();
sort(count.begin(), count.end(), cmp);
size = s.size();
}
//If there're more chars in count to output.
bool has_more() {
return size > 0;
}
//Output one char in count and reduce available size. The order matters.
char next_char() {
assert(pos < count.size() && size > 0 && count[pos].second > 0);
char ret = count[pos].first;
if (--count[pos].second == 0)
++pos;
--size;
return ret;
}
static bool cmp(const CharCount & a, const CharCount & b) {
return (a.second > b.second) || (a.second == b.second && a.first < b.first);
}
string solve(const string & s, int k) {
assert(k > 0);
if (k > 26 || k >= s.size())
return "";
count_char(s);
//Divide the chars into groups with k chars in each group, only the last
//group may has less than k chars.
int groups = s.size() / k;
if (s.size() % k > 0)
groups++;
//If a char count is more than the number of groups, it means the char
//must appear at least twice in one group and thus it's impossible to
//ensure the distance k.
for (int i = 0; i < count.size(); i++) {
if (count[i].second > groups)
return "";
}
vector<char> ret(s.size());
int p = 0;
while (has_more()) {
assert(p < k);
//Fill position p in each group with the next_char().
for (int i = 0; i < groups && has_more(); i++) {
int idx = i * k + p;
if (idx >= ret.size())
break;
ret[idx] = next_char();
}
//Next position in each group to fill a char.
p++;
}
return string(ret.begin(), ret.end());
}
};
int main() {
string s;
int k;
while (cin >> s >> k) {
Solution so;
string r = so.solve(s, k);
if (r.empty())
cout << "Impossible";
else
cout << r;
cout << endl;
}
return 0;
}

The basic idea is to divide the chars from string s into n groups, each with k chars(only the last may has less than k chars). Then fill the position p(initially 0) of each group with the char of the most frequency, then the char of the less frequency and so on. When position p in each group is filled, ++p and repeat the procedure until all chars from s are filled in new container.