# 28.11.2023 [2147. Number of Ways to Divide a Long Corridor]
Count ways to place borders separating pairs of 'S' in 'SP' string
28.11.2023
2147. Number of Ways to Divide a Long Corridor hard
blog post
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/419
Problem TLDR
Count ways to place borders separating pairs of ‘S’ in ‘SP’ string
Intuition
We can scan linearly and do the interesting stuff after each two ‘S’: each new ‘P’ adds ‘sum’ ways to the total.
The last pair of ‘S’ don’t need a border.
// ssppspsppsspp
// ss 1
// ssp 2
// sspp 3
// sps 3
// spsp 3+3=6
// spspp 6+3=9 <-- return this
// ss 9
// ssp 9+9=18
// sspp 18+9=27 discard this result, as it is last
Approach
Careful what ‘sum’ to add, save the last sum to a separate variable.
Complexity
Time complexity:
O(n)Space complexity:
O(1)
Code
fun numberOfWays(corridor: String): Int {
var prev = 1
var sum = 1
var s = 0
for (c in corridor)
if (c == 'S') {
if (s == 2) {
prev = sum
s = 0
}
s++
} else if (s == 2)
sum = (prev + sum) % 1_000_000_007
return if (s == 2) prev else 0
}