<p>Along a long library corridor, there is a line of seats and decorative plants. You are given a <strong>0-indexed</strong> string <code>corridor</code> of length <code>n</code> consisting of letters <code>&#39;S&#39;</code> and <code>&#39;P&#39;</code> where each <code>&#39;S&#39;</code> represents a seat and each <code>&#39;P&#39;</code> represents a plant.</p>

<p>One room divider has <strong>already</strong> been installed to the left of index <code>0</code>, and <strong>another</strong> to the right of index <code>n - 1</code>. Additional room dividers can be installed. For each position between indices <code>i - 1</code> and <code>i</code> (<code>1 &lt;= i &lt;= n - 1</code>), at most one divider can be installed.</p>

<p>Divide the corridor into non-overlapping sections, where each section has <strong>exactly two seats</strong> with any number of plants. There may be multiple ways to perform the division. Two ways are <strong>different</strong> if there is a position with a room divider installed in the first way but not in the second way.</p>

<p>Return <em>the number of ways to divide the corridor</em>. Since the answer may be very large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>. If there is no way, return <code>0</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/04/1.png" style="width: 410px; height: 199px;" />
<pre>
<strong>Input:</strong> corridor = &quot;SSPPSPS&quot;
<strong>Output:</strong> 3
<strong>Explanation:</strong> There are 3 different ways to divide the corridor.
The black bars in the above image indicate the two room dividers already installed.
Note that in each of the ways, <strong>each</strong> section has exactly <strong>two</strong> seats.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/04/2.png" style="width: 357px; height: 68px;" />
<pre>
<strong>Input:</strong> corridor = &quot;PPSPSP&quot;
<strong>Output:</strong> 1
<strong>Explanation:</strong> There is only 1 way to divide the corridor, by not installing any additional dividers.
Installing any would create some section that does not have exactly two seats.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/12/3.png" style="width: 115px; height: 68px;" />
<pre>
<strong>Input:</strong> corridor = &quot;S&quot;
<strong>Output:</strong> 0
<strong>Explanation:</strong> There is no way to divide the corridor because there will always be a section that does not have exactly two seats.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == corridor.length</code></li>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>corridor[i]</code> is either <code>&#39;S&#39;</code> or <code>&#39;P&#39;</code>.</li>
</ul>

/*
class Solution {
    int mod = 1e9+7;
    int solve(int i, int j , string &corridor,int count , vector<int> &dp){
        int n = corridor.size();
        if (i>j) {
           return 1;
        }
        if(dp[i]!= -1){
            return dp[i];
        }
        int ans = 0;
        count = 0;  // To count 'S' characters
        for (int k = i; k <= j; k++) {
            if (corridor[k] == 'S') count++;
            if (count == 2) {
                ans = (ans + solve(k + 1, j, corridor,count, dp) % mod) % mod;
            }
            else if(count>2)
             return 0;
        }
        return dp[i]= ans%mod;
    }
public:
    int numberOfWays(string corridor) {
        int n = corridor.size();
          int count = 0;
        for (char c : corridor) {
            if (c == 'S') count++;
        }
        if (count < 2 || count % 2 != 0) return 0; // Edge case handling
        vector<int> dp(n, -1);
        return solve(0,n-1,corridor,0,dp);
    }
}; */

/*At First sight you may think like i will choose where to partion and use front partition DP and blah.. blah.. blah...

But hold on dear,
have you looked at constraints ?
it will cost you o(n^2) and n is about 1e5 , then how it will work ?

for front partition DP , your n should be about 1e3.
it will be solved by greedy */
class Solution {
public:

   
    int numberOfWays(string cr) {

        int n = cr.size();
        int md = 1e9 + 7; 
        int cnt = 0; 
        int temp = 1; 

        vector < int > arr;
        for(int i = 0 ; i < cr.size() ; i++){
            if(cr[i] == 'S') cnt++; 
            cnt %=2; 
            if(cnt == 0 && cr[i] == 'P') temp++; 
            else{
                arr.push_back(temp); 
                temp = 1; 
            }
        }

        long long ans = 1; 
        if(arr.size() <= 1 || cnt == 1) return 0; 
        for(int i = 1 ; i < arr.size() ; i++){
                ans= ( ans % md * arr[i] % md) % md; 
        }
        return ans; 


    }
};
71425