I am trying to rearrange a given string, so no two adjacent letters are the same.

For that I'm thinking to count every distinct letter's occurence, and then rearrange the string the characters occurence number

example:

Input: AABAABBC

Output: AAAABBBC

and after that spliting it in 2 different strings

AAAA BBBC

and then trying to get the final result.

My question is how do I rearrange the string like in the first example?

Here is my code so far:

private static string GetDistinctChars(string text)
{
    string result = "";
    foreach (char c in text)
    {
        if (!result.Contains(c))
        {
            result  = c;
        }
    }

    return result;
}

private static double GetCharOccurrence(string text, char charToCount)
{
    int count = 0;
    foreach (char c in text)
    {
        if (c == charToCount)
        {
            count  ;
        }
    }

    return count;
}

CodePudding user response：

You can do it like that:

string example = "AABBAACDCAA";

var orderList = example.OrderBy(x => x).ToList();

List<string> letters = new List<string>();
string temp = string.Empty;
for(int i = 0; i < orderList.Count; i  )
{
    temp  = orderList[i];
    if (i   1 == orderList.Count)
    {
        letters.Add(temp);
        break;
    }

    if(orderList[i] != orderList[i   1])
    {
        letters.Add(temp);
        temp = string.Empty;
    }
}

string result = String.Join(" ", letters);

Console.WriteLine(result);

If you don't want to use Linq Order by method, you should implement sorting algorithm like this:

static char[] SortArray(char[] array)
{
    int length = array.Length;

    char temp = array[0];

    for (int i = 0; i < length; i  )
    {
        for (int j = i   1; j < length; j  )
        {
            if (array[i] > array[j])
            {
                temp = array[i];

                array[i] = array[j];

                array[j] = temp;
            }
        }
    }

    return array;
}

and use it in your program:

string example = "AABBAACDCAA";

var orderList = SortArray(example.ToCharArray());

List<string> letters = new List<string>();
string temp = string.Empty;
for(int i = 0; i < orderList.Length; i  )
{
    temp  = orderList[i];
    if (i   1 == orderList.Length)
    {
        letters.Add(temp);
        break;
    }

    if(orderList[i] != orderList[i   1])
    {
        letters.Add(temp);
        temp = string.Empty;
    }
}

string result = String.Join(" ", letters);

Console.WriteLine(result);

alternativly, if you don't want to use list anymore, you can operate only on strigns:

string example = "AABBAACDCAA";

var orderList = SortArray(example.ToCharArray());

string lettersString = string.Empty;
for (int i = 0; i < orderList.Length; i  )
{
    lettersString  = orderList[i];
    if (i   1 == orderList.Length)
        break;

    if (orderList[i] != orderList[i   1])
        lettersString  = " ";
}

Console.WriteLine(lettersString);

CodePudding user response：

You can find your problem on LeetCode, it's a problem #767.

My algorithm is

1. If we have too many of same characters, we can't solve the problem (e.g. "aaaaaabc")
2. If solution exists, we can sort characters aababc -> aaabbc and then take item by item from the beginning and from the center:

For instance:

aababc -> aaabbc (ordered by frequency: a appears 3 time, b - 2, c - 1)

then

aaabbc      => ab
^  ^
take these  

aaabbc      => abab
 ^  ^
take these 

aaabbc      => ababac <- final answer
  ^  ^
take these

Code:

    using System.Linq;
    using System.Text;

    ...

    public static string ReorganizeString(string s) {
        int count = s.GroupBy(c => c).Max(g => g.Count());
        
        // One of the item is too frequent, no solutions 
        if (count > (s.Length   1) / 2)
            return "";
        
        string st = string.Concat(s
            .GroupBy(c => c)
            .OrderByDescending(g => g.Count())
            .ThenBy(g => g.Key) // not required, just for aesthetic
            .SelectMany(c => c));
        
        StringBuilder sb = new StringBuilder(s.Length);
    
        for (int i = 0; i < s.Length / 2;   i) {
            sb.Append(st[i]);
            sb.Append(st[(st.Length   1) / 2   i]);
        }
        
        // Middle character 
        if (s.Length % 2 != 0)
            sb.Append(st[st.Length / 2]);
        
        return sb.ToString();
    }

Demo:

string value = "AABAABBC";

Console.Write(ReorganizeString(value));

Output:

ABABABAC

Fiddle it yourself.

Edit: If StringBuilder (as well as System.Text) is really forbidden, we can use string, which, however, slows down the routine:

    using System.Linq;
    ...

    public static string ReorganizeString(string s) {
        int count = s.GroupBy(c => c).Max(g => g.Count());
        
        // One of the item is too frequent, no solutions 
        if (count > (s.Length   1) / 2)
            return "";
        
        string st = string.Concat(s
            .GroupBy(c => c)
            .OrderByDescending(g => g.Count())
            .ThenBy(g => g.Key) // not required, just for aesthetic
            .SelectMany(c => c));
        
        string result = "";
    
        for (int i = 0; i < s.Length / 2;   i) {
            result  = st[i];
            result  = st[(st.Length   1) / 2   i];
        }
        
        // Middle character 
        if (s.Length % 2 != 0)
            result  = st[st.Length / 2];
        
        return result;
    }