Rearrange a string so that all same characters become atleast d distance away - GeeksforGeeks

Rearrange a string so that all same characters become atleast d distance away - GeeksforGeeks
Given a string and a positive integer d, rearrange characters of the given string such that the same characters become at-least d distance away from each other.
Note that there can be many possible rearrangements, the output should be one of the possible rearrangements. If no such arrangement is possible, that should also be reported.
Expected time complexity is O(n) where n is length of input string.

// The function returns next eligible character

// with maximum frequency (Greedy!!) and

// zero or negative distance

int nextChar(int freq[], int dist[])

{

    int max = INT_MIN;

    for (int i = 0; i < MAX_CHAR; i++)

        if (dist[i] <= 0 && freq[i] > 0 &&

        (max == INT_MIN || freq[i] > freq[max]))

                max = i;

 

    return max;

}

 

// The main function that rearranges input string 'str'

// such that two same characters become atleast d

// distance away

int rearrange(char str[], char out[], int d)

{

    // Find length of input string

    int n = strlen(str);

 

    // Create an array to store all characters and their

    // frequencies in str[]

    int freq[MAX_CHAR] = { 0 };

 

    // Traverse the input string and store frequencies

    // of all characters in freq[] array.

    for (int i = 0; i < n; i++)

        freq[str[i]]++;

 

    // Create an array for inserting the values at

    // correct distance dist[j] stores the least distance

    // between current position and the next position we

    // can use character 'j'

    int dist[MAX_CHAR] = { 0 };

 

    for (int i = 0; i < n; i++)

    {

        // find next eligible character

        int j = nextChar(freq, dist);

 

        // return 0 if string cannot be rearranged

        if (j == INT_MIN)

            return 0;

 

        // Put character j at next position

        out[i] = j;

 

        // decrease its frequency

        freq[j]--;

 

        // set distance as d

        dist[j] = d;

 

        // decrease distance of all characters by 1

        for (int i = 0; i < MAX_CHAR; i++)

            dist[i]--;

    }

 

    // null terminate output string

    out[n] = '\0';

 

    // return success

    return 1;

}

Read full article from Rearrange a string so that all same characters become atleast d distance away - GeeksforGeeks