Chuỗi con nhỏ nhất có thể được thay thế để làm cho chuỗi có cùng số của mỗi ký tự

Question

Tôi đang cố giải quyết vấn đề gần như chính xác. Cụ thể, tôi được cung cấp một chuỗi s sao cho s.Length % 4 == 0 và mỗi s[i] là một trong số 'A', 'C', 'T' hoặc 'G'. Tôi muốn tìm chuỗi con nhỏ nhất mà tôi có thể thay thế sao cho mỗi của 'A', 'C', 'T' và 'G' xuất hiện chính xác s.Length/4 lần.

Ví dụ: với s="GAAATAAA", một giải pháp tối ưu là thay thế chuỗi con "AAATA" bằng "TTCCG", dẫn đến "GTTCCGAA".

Tôi đã giải thích cách tiếp cận của mình trong các nhận xét bên dưới và tôi tự hỏi liệu nó có phải là chính xác hay không trong đó nó sẽ đưa tôi đến câu trả lời đúng.

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

Nếu chuỗi đã có bộ ký tự cân bằng thì bạn đã hoàn thành và không phải làm gì cả.

Nếu không, bạn luôn có thể giải quyết sự cố bằng cách thay thế các ký tự bằng 0 là số tối thiểu. Bạn làm điều này bằng cách thêm bất kỳ ký tự nào bị thiếu. Vì vậy, ví dụ như để có trường hợp thử nghiệm của bạn:

GAAATAAA

Nhân vật với hầu hết các lần xuất hiện là A với 6. Bạn cần 5 thêm G, 5 thêm T và thêm 6 C. Vì vậy, thay thế một A với các nhân vật cần thiết bao gồm A chính nó:

GAAATAA [AGGGGGTTTTTCCCCCC]

Kể từ A ban đầu được thay thế bằng một A, bạn đã thực sự thay thế không ký tự, tối thiểu có thể.

Answer 2

Tôi nghĩ giải pháp của bạn sẽ hoạt động nhưng độ phức tạp của nó quá cao.
Đây là giải pháp thay thế
Nếu tính các ký tự trong chuỗi của bạn trả về {'A', 4}, {'C', 6}, {'G', 6}, {'T', 4} chuỗi con phải bắt đầu bằng C hoặc G, kết thúc bằng C hoặc G và có độ dài> = 2
Vì vậy, những gì chúng ta cần làm là lấy từng chuỗi xác minh những điều kiện đó, kiểm tra xem nó có chứa 'các ký tự xấu' trong trường hợp của chúng ta không C và một G. Nếu chiều dài của nó = 2 chúng tôi giành chiến thắng nếu không chúng tôi lưu trong một biến tạm thời và tiếp tục thử nghiệm của chúng tôi

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


} 

tôi thực hiện một số điều chỉnh để xử lý các trường hợp đường biên giới. Đây là một số mẫu thử nghiệm và kết quả mà tôi nhận được có vẻ tốt

Answer 3

Suy nghĩ? Xin lỗi cho cả mã lộn xộn + giải pháp python. Ban đầu tôi bắt đầu viết nó trên điện thoại và cảm thấy lười biếng.

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

Cảm ơn @AnotherGeek cho đầu vào thử nghiệm! Đây là kết quả đầu ra.

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) 

Tôi nhận thấy điều này khá không hiệu quả. Bất kỳ đề xuất cải tiến nào?