Sections of Two Seats

Hard

A long waiting hall is described by a string hall: 'S' is a seat and 'P' is a potted plant. Two dividers already stand at the ends of the hall, left of the first position and right of the last. Between any two neighbouring positions you may place at most one extra divider. Place them so that every resulting section has exactly two seats (with any number of plants). Count the number of ways. Two ways differ if some spot has a divider in one and not in the other. If there is no way, return 0. Return the answer modulo 10⁹ + 7.

Example 1

hall="SPSPPSS" → 3

The first section is "SPS" and the second is "SS". Two plants lie between them, so the divider can go in any of three places.

Example 2

hall="PSPSP" → 1

Exactly two seats, so no extra dividers are needed: one way.

Example 3

hall="SSS" → 0

The number of seats is odd, so no division works.

Constraints

1 ≤ len(hall) ≤ 10⁵
hall[i] is either 'S' or 'P'

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Math String Dynamic Programming

Similar problems

Numbers From Working Keys Hard Flip the Circuit Output Hard Grading the Arithmetic Quiz Hard Numbers With a Digit Sum in Bounds Hard Tail to the Front Hard

Input

hall="SPSPPSS"

Expected

Run checks the first 3 tests in your browser. Submit checks all 148 tests on the server, hidden ones included.