सभी चुनौतियाँ
मध्यम 0 हल किए गए 0% स्वीकृति

DNA के Short Tandem Repeats गिनिए

हर short tandem repeat के लिए DNA अनुक्रम में लगातार आने वाली प्रतियों की सबसे लंबी श्रृंखला ढूँढिए।

आप क्या सीखेंगे

  • String के किसी substring की तुलना pattern से करना
  • किसी स्थान से शुरू होकर लगातार आने वाली प्रतियाँ गिनना
  • हर pattern की सबसे अच्छी गिनती याद रखना

समस्या

फ़ॉरेंसिक लैब लोगों की तुलना 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 अक्षर हैं

उदाहरण

उदाहरण 1
इनपुट:
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 है।

उदाहरण 2
इनपुट:
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 के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

हर कोडर का सबसे अच्छा पास हुआ समाधान। तेज़, कम मेमोरी वाले और बेहतर रेटिंग वाले समाधान ऊपर रहते हैं।

अभी कोई पास हुआ समाधान नहीं है। इसे हल करें और पहला स्थान पाएँ।

दूसरों से सीखें

समुदाय समाधान

अभी तक कोई प्रकाशित समाधान नहीं। पहला साझा करने के लिए इस चुनौती को हल करें।