समस्या
एक प्रायिकता (probability) लैब सिक्के को कई बार उछालती है और नतीजों को H (heads, चित) और T (tails, पट) की string के रूप में लिखती है। श्रृंखला (streak) लगातार एक जैसे नतीजों का सबसे बड़ा समूह है; HHTHHH में श्रृंखलाएँ HH, T और HHH हैं। छात्र अक्सर हैरान होते हैं कि किसी random रिकॉर्ड में सबसे लंबी श्रृंखला कितनी लंबी होती है, इसलिए लैब इसे मापती है।
coin_toss_streaks(tosses) लिखिए।
इनपुट
tosses: नतीजे क्रम से, सिर्फ़ H और T से बने।
आउटपुट
[longest_heads, longest_tails, streaks] लौटाइए: heads की सबसे लंबी श्रृंखला की लंबाई, tails की सबसे लंबी श्रृंखला की लंबाई (अगर वह पहलू कभी न आए तो 0), और श्रृंखलाओं की कुल संख्या।
सीमाएँ
0 ≤ tosses की लंबाई ≤ 100,000
उदाहरण
इनपुट:
tosses = "HHTHHH"
अपेक्षित आउटपुट:
expected = [3, 1, 3]
इनपुट:
std::string tosses = "HHTHHH";
अपेक्षित आउटपुट:
std::vector<long long> expected = {3, 1, 3};
इनपुट:
string tosses = "HHTHHH";
अपेक्षित आउटपुट:
long[] expected = new long[] {3, 1, 3};
व्याख्या
श्रृंखलाएँ HH, T और HHH हैं, इसलिए heads की सबसे लंबी श्रृंखला 3, tails की सबसे लंबी 1 है, और कुल 3 श्रृंखलाएँ हैं।
इनपुट:
tosses = "TTTT"
अपेक्षित आउटपुट:
expected = [0, 4, 1]
इनपुट:
std::string tosses = "TTTT";
अपेक्षित आउटपुट:
std::vector<long long> expected = {0, 4, 1};
इनपुट:
string tosses = "TTTT";
अपेक्षित आउटपुट:
long[] expected = new long[] {0, 4, 1};
व्याख्या
Heads कभी नहीं आता, इसलिए उसकी सबसे लंबी श्रृंखला 0 है; tails की लंबाई 4 वाली एक श्रृंखला है: [0, 4, 1]।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
नई श्रृंखला index 0 पर शुरू होती है और वहाँ भी जहाँ कोई नतीजा पिछले से अलग हो।
संकेत 2
heads के लिए एक और tails के लिए एक सबसे अच्छी लंबाई रखिए।
संकेत 3
खाली string में कोई श्रृंखला नहीं होती।
अपेक्षित जटिलता
समय O(n), अतिरिक्त स्थान O(1)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।