Smallest substring that can be replaced to make the string have the same number of each character
<p>I'm trying to solve a problem that is almost exactly that. In particular I'm given a string <code>s</code> such that <code>s.Length % 4 == 0</code> and each <code>s[i]</code> is one of <code>'A'</code>, <code>'C'</code>, <code>'T'</code> or <code>'G'</code>. I want to find the smallest substring that I can replace so that each of <code>'A'</code>, <code>'C'</code>, <code>'T'</code> and <code>'G'</code> appears exactly <code>s.Length / 4</code> times. </p>

<p>For example, with <code>s="GAAATAAA"</code>, one optimal solution is to replace a substring <code>"AAATA"</code> with <code>"TTCCG"</code>, resulting in <code>"GTTCCGAA"</code>.</p>

<p>I've decribed my approach in the comments below and I'm wondering whether it's genereally correct in that it will get me to the correct answer.</p>

<pre><code>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&lt;char,int&gt;() {
            { 'A', 0 }, { 'C', 0 }, { 'G', 0 }, { 'T', 0 }
        };
        for(int i = 0; i &lt; s.Length; ++i)
                counter[s[i]] += 1;

        int div = s.Length / 4;

        var pairs = counter.ToList();
        if(pairs.All(p =&gt; 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 -&gt; 3, T -&gt; 5, C -&gt; 2, G -&gt; 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" --&gt; "ACC" 
        // "GTG" --&gt; "ACC"
        // "GGT" --&gt; "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" --&gt; "AGCC"
        // "GTGG" --&gt; "AGCC"
        // "GGTG" --&gt; "AGCC"
        // "GGGT" --&gt; "AGCC"
        // "TTGG" --&gt; "ATCC"
        // "TGTG" --&gt; "ATCC"
        // "GTGT" --&gt; "ATCC"
        // "GGTT" --&gt; "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);
    }
}
</code></pre>