問題
確率の実験で、コインを何度も投げて結果を H(表)と T(裏)の文字列として記録しています。ここでいう「連続」とは、同じ結果が続くできるだけ長いかたまりのことで、HHTHHH には HH、T、HHH の3つの連続があります。ランダムな記録の中の最長連続が意外と長いことに生徒はよく驚くので、実験ではそれを測っています。
coin_toss_streaks(tosses) を実装してください。
入力
tosses: 結果を順に並べたもの。H と T だけからなります。
出力
表の最長連続の長さ、裏の最長連続の長さ(一度も出なければ0)、連続の総数を [longest_heads, longest_tails, streaks] として返してください。
制約
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 なので、表の最長連続は3、裏の最長連続は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};
解説
表は一度も出ないので最長連続は0です。裏の連続が長さ4で1つあるので [0, 4, 1] です。
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
新しい連続は、添字0と、直前の結果と異なる位置で始まります。
ヒント 2
表と裏それぞれについて、最長の長さを1つずつ記録しましょう。
ヒント 3
空文字列には連続が1つもありません。
目安の計算量
時間 O(n)、追加メモリ O(1)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。