簡単 0件解決済み 正答率0%

Coin Toss Streaks

Find the longest streak of heads, the longest streak of tails and the number of streaks in a coin toss record.

このチャレンジで学べること

  • Split a sequence into maximal runs
  • Track the best run for each value
  • Count runs

問題

翻訳を表示

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

例

例 1
入力:
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.

例 2
入力:
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 つずつ開いてみましょう。

ヒント 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用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

まだ合格した解答はありません。解いて 1 位になりましょう。

他の人の解答から学ぶ

コミュニティの解答

まだ公開された解答がありません。この課題を解いて最初の解答を共有しましょう。