可以替换的最小子字符串使字符串具有相同数量的每个字符

Question

我正试图解决几乎就是这个问题.特别是我给一个字符串s,使得s.Length % 4 == 0各s[i]是一个'A','C','T'或'G'.我想找到我可以更换,使每个最小子'A','C','T'并'G'准确显示s.Length / 4时间.

例如,使用s="GAAATAAA"中,一个最佳的解决方案是更换一个子"AAATA"带"TTCCG",从而产生"GTTCCGAA".

我在下面的评论中描述了我的方法,我想知道它是否真的正确,因为它会让我得到正确的答案.

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
class Solution
{
    static string ReplacementForSteadiness(string s)
    {   
        var counter = new Dictionary<char,int>() {
            { 'A', 0 }, { 'C', 0 }, { 'G', 0 }, { 'T', 0 }
        };
        for(int i = 0; i < s.Length; ++i)
                counter[s[i]] += 1;

        int div = s.Length / 4;

        var pairs = counter.ToList();
        if(pairs.All(p => p.Value == div))
            return "";

        // If here, that means there is an even count of characters in s. For example, if
        // s = "AAATGTTCTTGCGGGG", then counter = { A -> 3, T -> 5, C -> 2, G -> 6 },
        // div = 4, and we know that we need to increase the number of As by 1, decrease 
        // the number of Ts by 1, increase the number of Cs by 2 and decrease the number
        // of Gs by 2.

        // The smallest strings to replace will have 1 T and 2 Gs, to be replaced with 1 A and
        // 2 Cs (The order of characters in the replacement string doesn't matter).
        // "TGG" --> "ACC" 
        // "GTG" --> "ACC"
        // "GGT" --> "ACC"

        // None of those strings exist in s. The next smallest strings that could be replaced
        // would have 1 T and 3Gs, to be replaced with 1 A and 2 of the Gs to be replaced with
        // Cs. Or, 2 Ts and 2Gs, 1 of the Ts to be replaced by an A and both the Gs to be replaced
        // by Cs.
        // "TGGG" --> "AGCC"
        // "GTGG" --> "AGCC"
        // "GGTG" --> "AGCC"
        // "GGGT" --> "AGCC"
        // "TTGG" --> "ATCC"
        // "TGTG" --> "ATCC"
        // "GTGT" --> "ATCC"
        // "GGTT" --> "ATCC"

        // None of those strings exist in s. Etc.      

        string r;

        // ... 

        return r;
    }

    static void Main(String[] args)
    {
       Console.ReadLine(); // n
       string str = Console.ReadLine();
       string replacement = ReplacementForSteadiness(str);
       Console.WriteLine(replacement.Length);
    }
}

Answer 1

如果字符串已经具有平衡的字符集，那么您就完成了，无需执行任何操作。

否则，您始终可以通过替换最少的零个字符来解决问题。您可以通过添加缺少的任何字符来完成此操作。例如，以您的测试用例为例：

伽阿塔伽

出现次数最多的字符是 A，出现了 6 个。您需要 5 个额外的 G、5 个额外的 T 和 6 个额外的 C。因此，将一个 A 替换为所需的字符，包括 A 本身：

嘎阿塔阿[AGGGGGTTTTTCCCCCC]

由于原来的 A 被替换为 A，因此您实际上替换了零个字符，这是尽可能少的字符。