文字列が各文字の数と同じになるように置き換えることができる最小の部分文字列

Question

私はほぼ正確にその問題を解決しようとしています。特に私はのような文字列sを与えられ、それぞれは'A','C','T'または'G'のうちの1つです。私が置き換えることができる最小の部分文字列を見つけて、それぞれ'A','C','T'、'G'が正確にs.Length/4回現れるようにしたい。例えば

は、s="GAAATAAA"で一の最適解は"GTTCCGAA"その結果、"TTCCG"とサブ"AAATA"を交換することです。

私は以下のコメントに私のアプローチを書いてきましたが、私はそれが正しい答えに私を得ることが遺伝的に正しいかどうか疑問に思っています。

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

文字列にすでにバランスの取れた文字セットがある場合、完了したので何もする必要はありません。

そうしないと、最小のゼロ文字を置き換えることでいつでも問題を解決できます。これは、欠けている文字を追加することによって行います。だから、例えば、あなたのテストケースを取るために：ほとんどの出現と

文字が6である

GAAATAAAあなたは5追加のGさん、5追加のTさんと6追加のC年代を必要としています。だから、A自体を含む必要な文字を1つのAを置き換える：

GAAATAA [AGGGGGTTTTTCCCCCC]

元AがAで置き換えられているので、あなたが実際にゼロの文字、最小限に取って代わりました。

Answer 2

あなたのソリューションはうまくいくと思いますが、その複雑さは高すぎます。
代わりの解決方法があります
文字列内の文字数が{'A'、4}、{'C'、6}、{'G'、6}、{'T'、4} CまたはGで始まり、CまたはGで終わらなければならず、長さが2以上>
だから、これらの条件を検証する各文字列を取り、私たちのケースに「悪い文字」が含まれているかどうかをテストしますCと1 G. = 2その長さは、我々はそうでない場合、我々は、私はいくつかの変更がボーダーラインのケースを処理するために作られた一時変数に保存して、我々のテスト

using System; 
using System.Collections.Generic; 
using System.IO; 
using System.Linq; 
using System.Text; 
class Solution 
{ 
    static void Main(String[] args) 
    { 
     string[] inputs = { "GAAATAAA", "CACCGCTACCGC", "CAGCTAGC", "AAAAAAAA", "GAAAAAAA", "GATGAATAACCA", "ACGT" }; 

     List<string> replacement = new List<string>(); 
     foreach (var item in inputs) 
     { 
      replacement.Add(StringThatHasToBeReplaced(item)); 
     } 
    } 

    static string StringThatHasToBeReplaced(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.Where(p => p.Value != div).Count() == 0) 
     { 
      return null; 
     } 

     List<char> surplusCharacter = pairs.Where(p => p.Value > div).Select(p => p.Key).ToList(); 
     int minLength = pairs.Where(p => p.Value > div).Sum(p => p.Value - div); 
     string result = s; 
     for (int i = 0; i < s.Length - minLength + 1; i++) // i is the start index 
     { 
      if (surplusCharacter.Contains(s[i])) 
      { 
       if (minLength == 1) 
        return s[i].ToString(); 

       for (int j = i + minLength - 1; j < s.Length; j++) // j is the end index 
       { 
        if (surplusCharacter.Contains(s[j])) 
        { 
         var substring = s.Substring(i, j - i); 
         if (substring.Length >= result.Length) 
         { 
          break; 
         } 
         // we test if substring can be the string that need to be replaced 
         var isValid = true; 
         foreach (var c in surplusCharacter) 
         { 
          if (substring.Count(f => f == c) < counter[c] - div) 
          { 
           isValid = false; 
           break; 
          } 
         } 
         if (isValid) 
          result = substring; 
        } 
       } 
      } 
     } 
     return result; 
    } 


} 

を続ける勝った場合。 ここにいくつかのテストサンプルがあり、私がよく見える結果です

Answer 3

思考？厄介なコード+ pythonのソリューションの両方に申し訳ありません。私は最初、これを私の電話に書き始め、怠け者だと感じました。

import re 
from itertools import permutations 

def find_min(s): 
    freq = {ch:0 for ch in 'ATGC'} 
    for ch in s: 
     freq[ch] += 1 
    desired_len = int(len(s)/4) 
    fixes = {ch:desired_len-freq[ch] for ch in 'ATGC'} 
    replacement = '' 
    for ch in fixes: 
     adj = fixes[ch] 
     if adj < 0: 
      replacement += ch*(-1*adj) 
    perms = set(permutations(replacement)) 
    m = len(s) 
    to_replace = '' 
    for rep in perms: 
     regex = '.*?'.join([ch for ch in rep]) 
     finds = re.findall(regex,s) 
     if finds: 
      x = sorted(finds, key=lambda x:len(x))[0] 
      if m >= len(x): 
       m = len(x) 
       to_replace = x 

    print_replacement(s, to_replace, fixes) 

def print_replacement(inp, to_replace, fixes): 
    replacement = '' 
    for ch in to_replace: 
     if fixes[ch] > 0: 
      replacement += ch 
    for ch in fixes: 
     if fixes[ch] > 0: 
      replacement += ch*fixes[ch] 
    print('{0}\t\t- Replace {1} with {2} (min length: {3})'.format(inp ,to_replace, replacement, len(replacement))) 


def main(): 
    inputs = ["GAAATAAA", "CACCGCTACCGC", "CAGCTAGC", "AAAAAAAA", "GAAAAAAA", "GATGAATAACCA", "ACGT"] 
    for inp in inputs: 
     find_min(inp) 

if __name__ == '__main__': 
    main() 

ありがとう@AnotherGeekテスト入力用！ここに出力があります。

GAAATAAA  - Replace AAATA with TCCGT (min length: 5) 
CACCGCTACCGC - Replace CACCGC with AGAGTT (min length: 6) 
CAGCTAGC  - Replace C with T (min length: 1) 
AAAAAAAA  - Replace AAAAAA with CCGGTT (min length: 6) 
GAAAAAAA  - Replace AAAAA with CCGTT (min length: 5) 
GATGAATAACCA - Replace ATGAA with TGCGT (min length: 5) 
ACGT   - Replace with (min length: 0) 

私はこれがかなり非効率的であることを実感します。改善提案？