String Reorder Distance Apart

Given a string of lowercase characters, reorder them such that the same characters are at least distance d from each other.

Input: { a, b, b }, distance = 2
Output: { b, a, b }

I think it’s quite an interesting question. So if you want to do some brainstorming and do not wish to spoil the fun, please feel free to do so and beware of the spoilers ahead.

*** Spoilers alert! ***
*** Spoilers alert! ***
*** Spoilers alert! ***

The solution below involves a greedy strategy, that is: The character that has the most duplicates has the highest priority of being chosen to put in the new list. If that character cannot be chosen (due to the distance constraint), we go for the character that has the next highest priority. We also use some tables to improve the efficiency. (i.e., keeping track of # of duplicates of each character.)

VN:F [1.9.22_1171]
Rating: 2.7/5 (30 votes cast)
String Reorder Distance Apart, 2.7 out of 5 based on 30 ratings

46 thoughts on “String Reorder Distance Apart

  1. hangyu

    hi, i feel difficult to understand your code. Could you explain a little bit. Or can you send me some webpage that i could refer to.

    Thanks

    VA:F [1.9.22_1171]
    0
  2. 1337c0d3r

    I am sorry that this post is not explained clearly as it's one of my older posts. Do you have a specific question? I'll try my best to help.

    VA:F [1.9.22_1171]
    0
  3. hangyu

    I do not quite understand this part of the code:
    excep[j] = true;
    if (used[j] <= 0) {
    ans[i] = j;
    freq[j]–;
    used[j] = d;
    done = true;
    }
    }
    for (int i = 0; i < 256; i++)
    used[i]–;

    Thanks

    VA:F [1.9.22_1171]
    0
  4. Tinus

    @ Akash,

    That's because your input has numbers.
    The find_max function only sets the frequencies for the lowercase letters, which causes the problem with your input.

    From what I see the create function does seem to be written to be able to deal with all 256 characters (i.e. size of freq array), an appropriate change to the for loop in find_max might fix it.

    VA:F [1.9.22_1171]
    0
  5. Anonymous

    I do not quite understand this part of the code EITHER:
    excep[j] = true;
    if (used[j] <= 0) {
    ans[i] = j;
    freq[j]–;
    used[j] = d;
    done = true;
    }
    }
    for (int i = 0; i < 256; i++)
    used[i]–;

    VA:F [1.9.22_1171]
    0
    1. Kalyan.srinivas

      used[] –>for inserting the values at correct distance. lets see what happens for a,b,b
      1. finds max occuring ..= ‘b’
      2.sets excep[‘b’]=true; and used[‘b’] =0 so used[‘b’]=2 ,so ans[0]=’b’ ,at the end used[‘b]=1;
      3.now freq[‘a’]= 1 , freq[‘b’]=1 ,so code picks first ‘a’ as contender
      4.sets excep[‘a’] =true (this array is for if freq[‘a’] is decremented but ‘a’ is still max occuring we will select the next contender as excep[‘a’]=true and this statement if (!excep[c] && freq[c] > 0 && freq[c] > max) evaluates to false.
      5.so going on used[‘a’]=0 so ,used [‘a’]=2 and ans[1]=’a’ at the end used[‘a]=1, used[‘b]=0;
      6.now max occuring is remaining element ‘b’ and as used[‘b’]=0 ,ans[2] =’b’,used[‘b’]=2(for further characters)
      7.loop ends our resultant array is ‘b’ ,’a’,’b’
      Hope i helped….

      VA:F [1.9.22_1171]
      +1
  6. Anonymous

    Hi,
    I am really enjoying your posts. One suggestion, can you make the code appear in one frame? because it is bit frustrating to use the scroll button to go to rightmost of the code.
    Thanks for all your effort. Keep it up.

    VA:F [1.9.22_1171]
    0
  7. Anonymous

    for all the chars
    int find_max(int *freq,bool excep[],char *str) {
    int max_i = -1;
    int max = -1;
    for(int i=0; *(str+i); i++) {
    if(!excep[*(str+i)] && freq[*(str+i)] > 0 && freq[*(str+i)] > max) {
    max = freq[*(str+i)];
    max_i = *(str+i);
    }
    }
    return max_i;
    }

    void createString(char *str,int d, char ans[]) {
    int size = strlen(str);
    int *freq = (int *)calloc(sizeof(int),256);

    for(int i = 0; *(str+i); i++) {
    freq[*(str+i)]++;
    }

    VA:F [1.9.22_1171]
    0
  8. Zhe

    I feel the code have some redundancy. Here is my modification about the original one.

    #include
    #include
    using namespace std;

    int find_max(int distance[], int freq[])
    {
    int max_i = -1;
    int max = -1;

    for (char c = ‘a’; c <= 'z'; c++)
    {
    if ((distance[c] max))
    {
    max_i = c;
    max = freq[c];
    }
    }

    return max_i;
    }

    void create(char *str, int d, char ans[])
    {
    int n = strlen(str);
    int freq[256] = {0};
    for (int i = 0; i < n; i++)
    freq[str[i]]++;

    int distance[256] = {0};
    for (int i = 0; i < n; i++)
    {
    int j = find_max(distance, freq);

    if (j == -1)
    {
    cout << "Error\n";
    return;
    }

    ans[i] = j;
    freq[j]–;
    distance[j] = d;

    for (int i = 0; i < 256; i++)
    distance[i]–;
    }

    ans[n] = '';
    }

    int main()
    {
    char str[] = "aaaabbbccceedd";
    char ans[100];
    int distance = 2;
    create(str, 2, ans);

    for (int i = 0; i < strlen(str); i++)
    cout << ans[i] << ", ";
    cout << "\n";

    return 0;
    }

    VA:F [1.9.22_1171]
    +2
    1. foolishcat

      I do not know why this if statement is not displayed correctly, try using words again:
      if ((distance[c] max))

      should be

      distance[c] is less than or equal to 0
      AND
      freq[c] is larger than max

      VA:F [1.9.22_1171]
      +2
    2. Brian

      try this input: “aaa”, d=5
      output should be “error”,
      however, your output would be “abc”

      because, in the second loop, distance[‘b’] = -1; frequency[‘b’] = 0,
      it satisfies the if condition, so max_i = ‘b’

      in the third loop, distance[‘c’] = -2, frequency[‘c’] = 0,
      so max_i = ‘c’

      VN:F [1.9.22_1171]
      0
  9. Shwetank Gupta

    Psuedo Code:
    ——————–
    1- Initial a[ 256 ] = {0};
    2. Traverse the array from i = 0 to n
    – Increment a[ input[ i ] ] on each character in input[ i ].
    3- Sort array ‘a’ .
    4- Traverse ‘a’ from 0 to 256
    start
    – j = 0, k = 0;
    – while( a[ i ] > 0)
    do
    input[ k ] = i; // i = ASCII value of character
    k = k + d; // d = input distance
    done
    j++;
    k = j;
    end
    5- input array has required output now.

    Let me know, if there is issue.

    VA:F [1.9.22_1171]
    0
    1. Shwetank Gupta

      Sorry, i missed one step
      – Sort array ‘a’ here we cannot sort the array as such and we need a structure with corresponding character and count values.
      Rest algo will be changed accordingly.

      VA:F [1.9.22_1171]
      0
    2. Shwetank Gupta

      Sorry, i missed one step
      – Sort array ‘a’ here we cannot sort the array as such and we need a structure with corresponding character and count values.
      Rest algo will be changed accordingly.

      It would be better if we do these operation in a BST with count for each char.

      VA:F [1.9.22_1171]
      +1
  10. Bruce Miller

    I solved this by splitting the string into a prefix (initially empty) and a tail (which is whittled away to add characters to the prefix). In each step, I find a character in the tail that I can add to the prefix and still keep it legal, then I try to permute the remaining characters in the (increasingly smaller) tail.

    // confirm prefix
    bool verify(const string& s, int d) {
    for (int i=0; i<s.size(); ++i) {
    for (int j=i+1; j<s.size() and j<i+d; ++j) if (s[i]==s[j]) return false;
    }
    return true;
    }

    // return a string consisting of prefix+permutation(tail) such that
    // identical characters are at least d distance apart, or null if not possible.

    std::string* spaceout(const string& prefix, const string& tail, int d) {
    int tailLen = tail.size();

    // we are done if we have reduced the tail to nothing
    if (tailLen==0) return new string(prefix);

    // try each element of tail in turn as next element of prefix
    for (int i=0; i<tailLen; ++i) {

    // first see if the new prefix is valid
    string newPrefix(prefix);
    newPrefix += tail.substr(i, 1); // try adding this character to prefix
    if (not verify(newPrefix, d)) continue; // violates distance

    // try to find a working tail for this new prefix
    string newTail(tail.substr(0, i));
    newTail += tail.substr(i+1,tailLen-i-1);
    string* result = spaceout(newPrefix, newTail, d);
    if (result) return result;
    }

    return NULL;
    }

    main() {
    string* fixed = spaceout("", "acbbcab", 3);

    if (fixed)
    cout << "Hello, sailor! ["<<*fixed<<"]"<<std::endl;
    else
    cout << "You lose!"<<endl;
    }

    VA:F [1.9.22_1171]
    0
    1. Bruce Miller

      My apologies for that last entry. This one is shorter and more efficient:

      // return a string consisting of prefix+permutation(tail) such that
      // identical characters are at least d distance apart, or null if not possible.

      std::string* spaceout(const string& prefix, const string& tail, int d) {
      int tailLen = tail.size();

      // we are done if we have reduced the tail to nothing
      if (tailLen==0) return new string(prefix);

      // try each element of tail in turn as next element of prefix
      for (int i=0; i=0 and (prefix.size()-j)<d; –j)
      if (tail[i]==prefix[j]) { valid=false; break; }
      if (not valid) continue;
      string newPrefix = prefix + tail[i];

      // remove tail[i] and try to find a working tail for this new prefix
      string newTail = tail.substr(0, i) + tail.substr(i+1,tailLen-i-1);
      string* result = spaceout(newPrefix, newTail, d);
      if (result) return result;
      }
      return NULL;
      }

      main() {
      string* fixed = spaceout("", "aaccbbb", 3);

      if (fixed)
      cout << "Hello, sailor! ["<<*fixed<<"]"<<std::endl;
      else
      cout << "You lose!"<<endl;
      }

      VA:F [1.9.22_1171]
      0
  11. Anand

    I have written a code that does the same. Can anyone help me with the testcases (A string for which distribution is possible). As far as I have made the calculation it is working well.

    It takes a character with maximum frequency and places it d distances away then it takes the next character and start filling from the location it has finished filling previous character. On overflowing the size it gets back to start from the location which is not filled.

    VA:F [1.9.22_1171]
    0
    1. 1337c0d3r Post author

      Thanks irvine.

      For your input “bbaaaccdd” and distance = 3, my code returns “abcadbacd”, which I believe is correct. By the way the solution you gave is for distance = 2, right?

      VN:F [1.9.22_1171]
      0
  12. langqinren

    my solution

    VA:F [1.9.22_1171]
    +1
  13. Anmol Dhuria

    #include

    using namespace std;
    int find(int f[],int prev[],int i,int d)
    {
    int j,max=0,index=-1;;
    for(j=0;j<26;j++)
    {
    if(max<f[j]&&prev[j]<=i-d)
    {
    max=f[j];
    index=j;
    }
    }
    if(index==-1)
    return -1;
    else
    {
    –f[index];
    return index;
    }
    }
    int main()
    {
    char s[]="aaabbccdd";
    int f[26]={0};
    int i=0,d=2;
    while(s[i])
    {
    ++f[s[i]-'a'];
    i++;
    }
    int n=i;
    char ans[n+1];
    int prev[26];
    for(i=0;i<26;i++)
    prev[i]=-d;
    for(i=0;i<n;i++)
    {
    int j=find(f,prev,i,d);
    if(j==-1)
    {
    cout<<-1;
    return 0;
    }
    prev[j]=i;
    ans[i]='a'+j;
    }
    ans[n]='';
    cout<<ans;
    return 0;
    }

    VN:F [1.9.22_1171]
    0
  14. Anmol Dhuria

    </#include

    using namespace std;
    int find(int f[],int prev[],int i,int d)
    {
    int j,max=0,index=-1;;
    for(j=0;j<26;j++)
    {
    if(max<f[j]&&prev[j]<=i-d)
    {
    max=f[j];
    index=j;
    }
    }
    if(index==-1)
    return -1;
    else
    {
    –f[index];
    return index;
    }
    }
    int main()
    {
    char s[]="aaabbccdd";
    int f[26]={0};
    int i=0,d=2;
    while(s[i])
    {
    ++f[s[i]-'a'];
    i++;
    }
    int n=i;
    char ans[n+1];
    int prev[26];
    for(i=0;i<26;i++)
    prev[i]=-d;
    for(i=0;i<n;i++)
    {
    int j=find(f,prev,i,d);
    if(j==-1)
    {
    cout<<-1;
    return 0;
    }
    prev[j]=i;
    ans[i]='a'+j;
    }
    ans[n]='';
    cout<

    VN:F [1.9.22_1171]
    0
  15. miscellanea

    VN:F [1.9.22_1171]
    0
  16. theOtherWC

    I’m still not sure why highest priority should be given to character that dulplicates the most times. I think the priority should be arbitrary here and there is no really optimal because the shift of an optimal is an optimal.

    VA:F [1.9.22_1171]
    0
  17. Dun

    excep[256] and used[256] have duplicate logic, I have a easier solution:


    int getMax(int freq[], int used[]) {
    int max = -1;
    int maxIndex = -1;
    for (int i =0; imax ) {
    max = freq[i];
    maxIndex = i;
    }
    }
    return maxIndex;
    }

    void create(char* str, int d, char ans[]) {
    int freq[256] = {0};
    int length = strlen(str);
    for (int i =0; i<length; i++) {
    freq[str[i]]++;
    }
    int used[256] = {0};
    for (int i =0; i<length; i++) {
    int c = getMax(freq, used);
    ans[i] = c;
    used[c]+=d;
    freq[c]--;
    for (int j = 0; j0){
    used[j]--;
    }
    }
    }
    ans[length]='';
    }

    VA:F [1.9.22_1171]
    +2
  18. Ralph

    mine. hope it helps

    VN:F [1.9.22_1171]
    0
    1. mophic yao

      actually, your code does not work. let’s see “ababcb”, run it, what’s going on?
      ouput is “ababbc”
      Therefore, the first step besides sort, need to sort by count

      VA:F [1.9.22_1171]
      0

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

*