如何实现无相邻重复字符的字符串重排？（不使用LinQ）

需要编写C#程序实现以下功能：

• 对用户输入的字符串进行字符重排，确保没有两个相同字符相邻
• 若无法实现符合要求的重排，则返回出现次数最多的字符
• 要求禁止使用LinQ

示例：

输入：tttesst → 输出：tetstst
输入：aaaabc → 输出：a

现有代码运行后输出e ss tttt，需要解决如何将分组后的相同子串合并成符合要求的无相邻重复字符串。

核心思路 #

1. 统计字符频次：遍历字符串，统计每个字符的出现次数，同时记录出现次数最多的字符及其频次。
2. 判断重排可行性：如果出现次数最多的字符的频次 > (总长度 + 1) / 2，则无法实现重排，直接返回该字符。
3. 交替构建结果：若可重排，先将频次最高的字符放置在偶数索引位置，再用剩余字符填充剩余的偶数位和奇数位，确保相同字符不相邻。

完整实现代码 #

using System;

class Program
{
    static void Main()
    {
        Console.Write("请输入字符串：");
        string input = Console.ReadLine();
        string result = RearrangeString(input);
        Console.WriteLine(result);
        Console.ReadLine();
    }

    static string RearrangeString(string input)
    {
        if (string.IsNullOrEmpty(input))
            return string.Empty;

        // 统计所有ASCII字符的出现次数
        int[] charCounts = new int[256];
        int maxCount = 0;
        char maxChar = '\0';
        int totalLength = input.Length;

        foreach (char c in input)
        {
            charCounts[c]++;
            if (charCounts[c] > maxCount)
            {
                maxCount = charCounts[c];
                maxChar = c;
            }
        }

        // 判断是否无法重排：最高频次超过总长度的一半（向上取整）
        if (maxCount > (totalLength + 1) / 2)
        {
            return maxChar.ToString();
        }

        // 构建重排后的字符数组
        char[] resultArray = new char[totalLength];
        int evenIndex = 0; // 偶数位置索引（0,2,4...）
        int oddIndex = 1;  // 奇数位置索引（1,3,5...）

        // 先放置频次最高的字符到偶数位
        while (charCounts[maxChar] > 0)
        {
            resultArray[evenIndex] = maxChar;
            evenIndex += 2;
            charCounts[maxChar]--;
        }

        // 填充剩余字符：先填剩余偶数位，再填奇数位
        for (int i = 0; i < 256; i++)
        {
            while (charCounts[i] > 0)
            {
                if (evenIndex < totalLength)
                {
                    resultArray[evenIndex] = (char)i;
                    evenIndex += 2;
                }
                else
                {
                    resultArray[oddIndex] = (char)i;
                    oddIndex += 2;
                }
                charCounts[i]--;
            }
        }

        return new string(resultArray);
    }
}

代码说明 #

• 字符统计：用长度为256的数组覆盖所有ASCII字符，遍历输入字符串完成计数，同时跟踪频次最高的字符。
• 可行性判断：比如总长度为7时，(7+1)/2=4，若某字符出现次数超过4，则无法通过重排让相同字符不相邻；像输入aaaabc总长度6，(6+1)/2=3，而a出现4次，直接返回a。
• 重排逻辑：先将高频字符放在偶数位，确保它们被隔开，再用剩余字符填充剩余位置，最终得到无相邻重复的字符串。

内容的提问来源于stack exchange，提问作者Raluca123