All challenges
Easy 0 solved 0% acceptance

Coin Toss Streaks

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

What you'll learn

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

Problem

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.

Constraints

0 ≤ length of tosses ≤ 100,000

Examples

Example 1
Input:
tosses = "HHTHHH"

Expected output:
expected = [3, 1, 3]
Input:
std::string tosses = "HHTHHH";

Expected output:
std::vector<long long> expected = {3, 1, 3};
Input:
string tosses = "HHTHHH";

Expected output:
long[] expected = new long[] {3, 1, 3};

Explanation

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.

Example 2
Input:
tosses = "TTTT"

Expected output:
expected = [0, 4, 1]
Input:
std::string tosses = "TTTT";

Expected output:
std::vector<long long> expected = {0, 4, 1};
Input:
string tosses = "TTTT";

Expected output:
long[] expected = new long[] {0, 4, 1};

Explanation

Heads never comes up, so its longest streak is 0; there is one tails streak of length 4: [0, 4, 1].

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

A new streak starts at index 0 and wherever a toss differs from the one before.

Hint 2

Keep one best length for heads and one for tails.

Hint 3

An empty string has no streaks at all.

Expected complexity

O(n) time, O(1) extra space

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.