Najmniejszy podłańcuch, który można zastąpić, aby ciąg zawierał taką samą liczbę znaków.

Question

Próbuję rozwiązać problem, który jest prawie dokładnie taki. W szczególności dostaję ciąg s taki, że s.Length % 4 == 0 i każdy s[i] jest jednym z 'A', 'C', 'T' lub 'G'. Chcę znaleźć najmniejszy podciąg, który można zastąpić, aby każdy z nich był wyświetlany dokładnie jeden raz.

Na przykład z s="GAAATAAA", jednym optymalnym rozwiązaniem jest zastąpienie podłańcucha "AAATA" przez "TTCCG", co daje "GTTCCGAA".

Opisałem moje podejście w komentarzach poniżej i zastanawiam się, czy jest on całkowicie poprawny, ponieważ doprowadzi mnie do prawidłowej odpowiedzi.

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

Jeśli łańcuch ma już zrównoważony zestaw znaków, oznacza to, że skończyłeś i nie musisz nic robić.

W przeciwnym razie zawsze możesz rozwiązać problem zastępując zero znaków, co jest minimum. Robisz to, dodając brakujące znaki. Tak na przykład, aby wziąć swój przypadek testowy:

GAAATAAA

Charakter większości zdarzeń jest A z 6. Trzeba dodatkowe 5 G, 5 dodatkowy T i 6 dodatkowych C-tych. Tak, wymień jeden A z potrzebnych znaków w tym samym A:

GAAATAA [AGGGGGTTTTTCCCCCC]

Ponieważ oryginalna A otrzymuje z A, zostały faktycznie zastąpione zero znaków, minimalne możliwe.

Answer 2

Myślę, że twoje rozwiązanie będzie działać, ale jego złożoność jest zbyt wysoka.
Oto alternatywne rozwiązanie:
Jeśli liczenie znaków w ciągu znaków zwraca {'A', 4}, {'C', 6}, {'G', 6}, {'T', 4} podłańcuch musi zaczynać się od C lub G, kończyć na C lub G i mieć długość> = 2
Musimy więc wziąć każdy ciąg, który sprawdza ten warunek, sprawdzić, czy zawiera on "złe znaki" w naszym przypadku jeden C i jeden G. Jeśli jego długość = 2 wygramy inaczej zapisać w zmiennej tymczasowej i kontynuować nasz test

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; 
    } 


} 

zrobiłem pewnych modyfikacji do obsługi przypadki graniczne. Oto przykładowa próbka, a wynik, który otrzymuję, wygląda dobrze

Answer 3

Myśli? Przepraszamy za kłopotliwy kod + rozwiązanie Pythona. Początkowo zacząłem pisać to na moim telefonie i czułem się leniwy.

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() 

Dzięki @AnotherGeek dla wejść testowych! Oto wyniki.

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) 

Zdaję sobie sprawę, że jest to cholernie mało wydajne. Jakieś sugestie ulepszeń?