Show problems as
Classic problem #1358MediumHash TableStringSliding Window

Number of Substrings Containing All Three Characters

Real-world version: Bay Coverage in the Parcel Log
Tracked in this browser only
Read Number of Substrings Containing All Three Characters on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A parcel hub sends every parcel down one of three chutes, which the crew label r, g and b. The shift log is a string log where the character at each position names the chute used by that parcel, in the order the parcels went through.

A stretch is any run of one or more consecutive positions of log. A stretch is covering when at least one parcel inside it went down each of the three chutes.

Count the covering stretches. Two stretches are different when they begin at different positions or end at different positions, even when they read the same. Return that count.

Examples

Example 1

Input
log = "gbrgb"
Output
6

Numbering the positions from 1, the covering stretches are 1-3, 1-4, 1-5, 2-4, 2-5 and 3-5. Each of those six holds a parcel for chute r, one for chute g and one for chute b.

Example 2

Input
log = "rrggrr"
Output
0

Chute b never appears in the log, so no stretch can hold a parcel for all three chutes.

Example 3

Input
log = "brrrbg"
Output
4

Chute g is used only by the last parcel, so a covering stretch has to end at position 6. The four that also reach back to an r and a b are 1-6, 2-6, 3-6 and 4-6.

Constraints

  • 3 <= log.length <= 5 * 10^4
  • log consists only of the characters 'r', 'g' and 'b'.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def count_full_stretches(log: str) -> int:
Java
public int countFullStretches(String log)

More on the same topics