समस्या
फ़ॉरेंसिक लैब लोगों की तुलना short tandem repeats (STRs) से करती हैं: ये DNA की छोटी इकाइयाँ होती हैं, जैसे AGAT, जो कई बार लगातार आती हैं। हर इकाई के लिए लैब पूरे अनुक्रम में कहीं भी लगातार प्रतियों की सबसे लंबी श्रृंखला दर्ज करती है। TTAGATAGATAGATCAGATAGAT में इकाई AGAT शुरुआत के पास तीन बार लगातार और बाद में दो बार आती है, इसलिए उसकी गिनती 3 है।
dna_str_count(sequence, repeats) लिखिए।
इनपुट
sequence: DNA अनुक्रम, जिसमें अक्षर A, C, G और T हैं।
repeats: STR इकाइयाँ जिन्हें मापना है।
आउटपुट
हर इकाई के लिए एक गिनती लौटाइए, उसी क्रम में जिसमें repeats हैं: लगातार आने वाली प्रतियों की सबसे बड़ी संख्या। जो इकाई कभी नहीं आती, उसकी गिनती 0 है।
सीमाएँ
0 ≤ sequence की लंबाई ≤ 5,000
1 ≤ इकाइयों की संख्या ≤ 10
हर इकाई में 1 से 8 अक्षर हैं
उदाहरण
इनपुट:
sequence = "TTAGATAGATAGATCAGATAGAT"
repeats = ["AGAT", "CA"]
अपेक्षित आउटपुट:
expected = [3, 1]
इनपुट:
std::string sequence = "TTAGATAGATAGATCAGATAGAT";
std::vector<std::string> repeats = {"AGAT", "CA"};
अपेक्षित आउटपुट:
std::vector<long long> expected = {3, 1};
इनपुट:
string sequence = "TTAGATAGATAGATCAGATAGAT";
string[] repeats = new string[] {"AGAT", "CA"};
अपेक्षित आउटपुट:
long[] expected = new long[] {3, 1};
व्याख्या
AGAT शुरुआत में 3 बार और अंत में सिर्फ़ 2 बार लगातार आता है, इसलिए उसका स्कोर 3 है; CA एक बार आता है, इसलिए उसका स्कोर 1 है।
इनपुट:
sequence = "AATGAATGAATGTATC"
repeats = ["AATG", "TATC", "GATA"]
अपेक्षित आउटपुट:
expected = [3, 1, 0]
इनपुट:
std::string sequence = "AATGAATGAATGTATC";
std::vector<std::string> repeats = {"AATG", "TATC", "GATA"};
अपेक्षित आउटपुट:
std::vector<long long> expected = {3, 1, 0};
इनपुट:
string sequence = "AATGAATGAATGTATC";
string[] repeats = new string[] {"AATG", "TATC", "GATA"};
अपेक्षित आउटपुट:
long[] expected = new long[] {3, 1, 0};
व्याख्या
AATG 3 बार दोहराया गया है, TATC एक बार और GATA कभी नहीं: [3, 1, 0]।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
किसी शुरुआती स्थान से, जब तक अगला टुकड़ा इकाई के बराबर है, इकाई की लंबाई जितना आगे कूदते रहिए।
संकेत 2
हर शुरुआती स्थान आज़माइए और सबसे लंबी श्रृंखला याद रखिए।
संकेत 3
जो इकाई कभी मेल नहीं खाती, उसकी सबसे अच्छी गिनती 0 ही रहती है।
अपेक्षित जटिलता
समय O(n × m × k), अतिरिक्त स्थान O(m)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।