<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 {
public:

int solve(int i,int ct, string &corridor,vector<vector<int>>&dp){
  if(i>=corridor.size()) return ct==2;
  if(dp[i][ct]!=-1) return dp[i][ct];
  int ans=0;
  if(ct==2){
    if(corridor[i]=='P'){
      ans=(solve(i+1,ct,corridor,dp)+solve(i+1,0,corridor,dp));
    } else{
      ans=solve(i+1,1,corridor,dp);
    }
  }else{
     if(corridor[i]=='P'){
      ans=solve(i+1,ct,corridor,dp);
    } else{
      ans=solve(i+1,ct+1,corridor,dp);
    }
  }
 return dp[i][ct]= ans%1000000007;
}
    int numberOfWays(string corridor) {
      vector<vector<int>>dp(corridor.size(),vector<int>(3,-1));
        return solve(0,0 ,corridor,dp);
    }
};

/**
 * 
 * k = current number of seats
 * i = current position
 * Time complexity = O(N)
 * 
**/
// class Solution {
// public:
//     const int MOD = (int)1e9 + 7;
//     long long dp[100001][3];
//     long long getAns(string & a, int i, int k) {
//         if(i >= a.size()) {
//             return k == 2;
//         }
        
//         if(dp[i][k] != -1)return dp[i][k];
        
// 		//if total number of seats in current segment is 2
//         if(k == 2) {
//             if(a[i] == 'P') {
// 				//choice either to add divider before current plant or not.
//                 return dp[i][k] = (getAns(a, i + 1, 0) % MOD + getAns(a, i + 1, k) % MOD) % MOD;
//             }
//             else {
// 				//necessary to put a divider before current seat, as current count of seat is 2
//                 return dp[i][k] = getAns(a, i + 1, 1) % MOD;
//             }
//         }
//         else {
// 			//current seat is less than 2 so, move ahead
//             return dp[i][k] = getAns(a, i + 1, k + (a[i] == 'S')) % MOD;
//         }
        
        
//     }
//     int numberOfWays(string corridor) {
//         memset(dp, -1, sizeof(dp));
//         return getAns(corridor, 0, 0); 
//     }
// };
190175