如何在不使用Linq的情况下重排字符串使相邻字符不重复

核心思路梳理 #

你的思路是可行的：先统计每个字符的出现次数，把字符按出现次数从多到少拼接成连续字符串（比如输入AABAABBC变成AAAABBBC），再拆成两部分，最后交叉合并得到相邻字符不重复的结果。不过要先做个前提判断：出现次数最多的字符，数量不能超过总长度的一半（向上取整），否则根本无法完成重排。

完整实现代码及步骤 #

1. 统计字符出现次数 #

用Dictionary<char, int>来统计，比你现有的两个方法效率高很多，不用反复遍历原字符串：

private static Dictionary<char, int> CountCharOccurrences(string text)
{
    Dictionary<char, int> charCounts = new Dictionary<char, int>();
    foreach (char c in text)
    {
        if (charCounts.ContainsKey(c))
        {
            charCounts[c]++;
        }
        else
        {
            charCounts.Add(c, 1);
        }
    }
    return charCounts;
}

2. 按出现次数降序排序字符 #

不用Linq的话，手动用选择排序对统计结果排序，把出现次数多的字符排前面：

private static List<KeyValuePair<char, int>> SortCharsByCountDesc(Dictionary<char, int> charCounts)
{
    List<KeyValuePair<char, int>> sortedList = new List<KeyValuePair<char, int>>(charCounts);
    // 选择排序实现降序排列
    for (int i = 0; i < sortedList.Count - 1; i++)
    {
        int maxIndex = i;
        for (int j = i + 1; j < sortedList.Count; j++)
        {
            if (sortedList[j].Value > sortedList[maxIndex].Value)
            {
                maxIndex = j;
            }
        }
        // 交换当前位置和最大次数的元素
        KeyValuePair<char, int> temp = sortedList[i];
        sortedList[i] = sortedList[maxIndex];
        sortedList[maxIndex] = temp;
    }
    return sortedList;
}

3. 生成连续拼接的字符串 #

把排序后的字符按次数重复拼接，比如AAAABBBC：

private static string BuildConcatenatedString(List<KeyValuePair<char, int>> sortedChars)
{
    StringBuilder sb = new StringBuilder();
    foreach (var pair in sortedChars)
    {
        sb.Append(new string(pair.Key, pair.Value));
    }
    return sb.ToString();
}

4. 拆分+交叉合并得到最终结果 #

先判断是否可重排，再拆分字符串，最后交替拼接两部分：

private static string RearrangeString(string text)
{
    if (string.IsNullOrEmpty(text)) return text;

    var charCounts = CountCharOccurrences(text);
    var sortedChars = SortCharsByCountDesc(charCounts);
    
    // 检查是否能重排：最多的字符数不能超过 (总长度+1)/2
    int maxCount = sortedChars[0].Value;
    int totalLength = text.Length;
    if (maxCount > (totalLength + 1) / 2)
    {
        return ""; // 无法重排时返回空，也可以改成自定义提示
    }

    string concatenated = BuildConcatenatedString(sortedChars);
    // 拆分：第一部分取前(总长度+1)/2个字符，保证最长的字符都在这部分
    int splitIndex = (totalLength + 1) / 2;
    string part1 = concatenated.Substring(0, splitIndex);
    string part2 = concatenated.Substring(splitIndex);

    // 交叉合并
    StringBuilder result = new StringBuilder();
    int i = 0, j = 0;
    while (i < part1.Length || j < part2.Length)
    {
        if (i < part1.Length)
        {
            result.Append(part1[i]);
            i++;
        }
        if (j < part2.Length)
        {
            result.Append(part2[j]);
            j++;
        }
    }

    return result.ToString();
}

测试示例 #

比如输入AABAABBC，调用RearrangeString后会得到ABABABAC（或其他符合要求的结果），相邻字符完全不重复。

对原有代码的优化说明 #

你原来的GetDistinctChars和GetCharOccurrence每次判断字符是否存在、统计次数都要遍历原字符串，效率偏低。改用Dictionary只遍历一次原字符串就能完成统计，性能提升明显。

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