The Number of Ways to Divide a Long Corridor problem gives you a corridor string with 'S' (seats) and 'P' (plants). You must divide it with dividers such that each section has exactly 2 seats. Count valid divider placements modulo 10^9+7. The key insight: after every 2nd seat, the space for placing dividers determines the number of ways.
Zomato asks this hard math/DP problem because the number of valid divider positions between consecutive pairs of seats can be computed by counting plants between the 2nd seat of one pair and the 1st seat of the next pair. The math, string, and dynamic programming interview pattern is the core.
Count positions between seat pairs. Scan the corridor string. Collect positions of all 'S' characters. If the total seat count is 0 or odd, return 0. Otherwise, for each consecutive pair (2i-th seat and (2i+1)-th seat), the number of valid divider positions = distance between them (number of plants between them plus 1). Multiply all these counts together.
corridor = "SSPPSPS". Seat positions: [0,1,4,6].
j - i (not j-i+1).This problem is a "multiply independent choices" problem: once you identify the valid divider positions between each consecutive seat pair, the total is the product of all local choices (since each divider position is independent). The key insight is counting only plants between the correct boundary seats. Practice similar "count ways to partition with constraints" problems — they often reduce to multiplying independent local choice counts along the structure.