Show problems as
Classic problem #1915MediumHash TableStringBit ManipulationPrefix Sum

Number of Wonderful Substrings

Real-world version: Nearly Even Telemetry Stretches
Tracked in this browser only
Read Number of Wonderful Substrings on LeetCode(opens in a new tab)

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

A probe reports ten kinds of event, written as the lowercase letters a through j. One session of reports arrives as the string stream, one character per event, in the order they happened.

A stretch is any non-empty contiguous run of the session. A stretch is nearly even when at most one of the ten kinds occurs an odd number of times inside it, so either every kind present occurs an even number of times, or exactly one kind occurs an odd number of times and all the others occur an even number of times.

Return how many nearly even stretches the session contains. Two stretches that cover different positions count separately even when they read the same.

Examples

Example 1

Input
stream = "efe"
Output
4

Four stretches are nearly even: each of the three single events, where the one kind present occurs once, and the whole session `efe`, where `e` occurs twice and `f` once.

Example 2

Input
stream = "gghg"
Output
7

Seven stretches are nearly even: the four single events, the stretch `gg` at indices 0 and 1 where `g` occurs twice, and the stretches `ggh` and `ghg`, each holding `g` twice and `h` once.

Example 3

Input
stream = "hiih"
Output
8

Eight stretches are nearly even, among them the whole session, where `h` occurs twice and `i` occurs twice, so no kind at all occurs an odd number of times.

Constraints

  • 1 <= stream.length <= 10^5
  • stream consists of the lowercase letters 'a' through 'j' only.
  • The count can exceed the range of a signed 32-bit integer; it stays below 10^11.

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_nearly_even(stream: str) -> int:
Java
public long countNearlyEven(String stream)

More on the same topics