समस्या
A probability lab flips a coin many times and writes the results as a string of H (heads) and T (tails). A streak is a maximal group of consecutive equal results; HHTHHH has the streaks HH, T and HHH. Students are often surprised how long the longest streak in a random record is, so the lab measures it.
Implement coin_toss_streaks(tosses).
Input
tosses: The results in order, using only H and T.
Output
Return [longest_heads, longest_tails, streaks]: the length of the longest heads streak, the length of the longest tails streak (0 if that side never comes up) and the total number of streaks.
सीमाएँ
0 ≤ length of 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};
व्याख्या
The streaks are HH, T and HHH, so the longest heads streak is 3, the longest tails streak is 1, and there are 3 streaks.
इनपुट:
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 never comes up, so its longest streak is 0; there is one tails streak of length 4: [0, 4, 1].
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
A new streak starts at index 0 and wherever a toss differs from the one before.
संकेत 2
Keep one best length for heads and one for tails.
संकेत 3
An empty string has no streaks at all.
अपेक्षित जटिलता
O(n) time, O(1) extra space
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।