2147. Number of Ways to Divide a Long Corridor - Explanation

class Solution:
    def numberOfWays(self, corridor: str) -> int:
        mod = 10**9 + 7
        cache = [[-1] * 3 for i in range(len(corridor))]  # (i, seats) -> count

        def dfs(i, seats):
            if i == len(corridor):
                return 1 if seats == 2 else 0
            if cache[i][seats] != -1:
                return cache[i][seats]

            res = 0
            if seats == 2:
                if corridor[i] == "S":
                    res = dfs(i + 1, 1)
                else:
                    res = (dfs(i + 1, 0) + dfs(i + 1, 2)) % mod
            else:
                if corridor[i] == "S":
                    res = dfs(i + 1, seats + 1)
                else:
                    res = dfs(i + 1, seats)

            cache[i][seats] = res
            return res

        return dfs(0, 0)

class Solution:
    def numberOfWays(self, corridor: str) -> int:
        MOD = 1000000007
        n = len(corridor)
        dp = [[0] * 3 for _ in range(n + 1)]
        dp[n][2] = 1

        for i in range(n - 1, -1, -1):
            for seats in range(3):
                if seats == 2:
                    if corridor[i] == 'S':
                        dp[i][seats] = dp[i + 1][1]
                    else:
                        dp[i][seats] = (dp[i + 1][0] + dp[i + 1][2]) % MOD
                else:
                    if corridor[i] == 'S':
                        dp[i][seats] = dp[i + 1][seats + 1]
                    else:
                        dp[i][seats] = dp[i + 1][seats]

        return dp[0][0]

class Solution:
    def numberOfWays(self, corridor: str) -> int:
        MOD = 1000000007
        dp = [0, 0, 1]

        for i in reversed(corridor):
            new_dp = [0] * 3
            for seats in range(3):
                if seats == 2:
                    new_dp[seats] = dp[1] if i == 'S' else (dp[0] + dp[2]) % MOD
                else:
                    new_dp[seats] = dp[seats + 1] if i == 'S' else dp[seats]
            dp = new_dp

        return dp[0]

class Solution:
    def numberOfWays(self, corridor: str) -> int:
        mod = 10**9 + 7
        seats = [i for i, c in enumerate(corridor) if c == "S"]

        length = len(seats)
        if length < 2 or length % 2 == 1:
            return 0

        res = 1
        for i in range(1, length - 1, 2):
            res = (res * (seats[i + 1] - seats[i])) % mod

        return res

class Solution:
    def numberOfWays(self, corridor: str) -> int:
        mod = 1_000_000_007
        count = 0
        res = 1
        prev = -1

        for i, c in enumerate(corridor):
            if c == 'S':
                count += 1
                if count > 2 and count % 2 == 1:
                    res = (res * (i - prev)) % mod
                prev = i

        return res if count >= 2 and count % 2 == 0 else 0