<p>Given a 2D character matrix <code>grid</code>, where <code>grid[i][j]</code> is either <code>&#39;X&#39;</code>, <code>&#39;Y&#39;</code>, or <code>&#39;.&#39;</code>, return the number of <span data-keyword="submatrix">submatrices</span> that contain:</p>

<ul>
	<li><code>grid[0][0]</code></li>
	<li>an <strong>equal</strong> frequency of <code>&#39;X&#39;</code> and <code>&#39;Y&#39;</code>.</li>
	<li><strong>at least</strong> one <code>&#39;X&#39;</code>.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">grid = [[&quot;X&quot;,&quot;Y&quot;,&quot;.&quot;],[&quot;Y&quot;,&quot;.&quot;,&quot;.&quot;]]</span></p>

<p><strong>Output:</strong> <span class="example-io">3</span></p>

<p><strong>Explanation:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2024/06/07/examplems.png" style="padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; width: 175px; height: 350px;" /></strong></p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">grid = [[&quot;X&quot;,&quot;X&quot;],[&quot;X&quot;,&quot;Y&quot;]]</span></p>

<p><strong>Output:</strong> <span class="example-io">0</span></p>

<p><strong>Explanation:</strong></p>

<p>No submatrix has an equal frequency of <code>&#39;X&#39;</code> and <code>&#39;Y&#39;</code>.</p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">grid = [[&quot;.&quot;,&quot;.&quot;],[&quot;.&quot;,&quot;.&quot;]]</span></p>

<p><strong>Output:</strong> <span class="example-io">0</span></p>

<p><strong>Explanation:</strong></p>

<p>No submatrix has at least one <code>&#39;X&#39;</code>.</p>
</div>

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

<ul>
	<li><code>1 &lt;= grid.length, grid[i].length &lt;= 1000</code></li>
	<li><code>grid[i][j]</code> is either <code>&#39;X&#39;</code>, <code>&#39;Y&#39;</code>, or <code>&#39;.&#39;</code>.</li>
</ul>

class Solution:
    def numberOfSubmatrices(self, grid: List[List[str]]) -> int:
        m,n = len(grid), len(grid[0]) if grid else 0
        ''' 
        X Y X  [0,T] [0,T] [1,T]
        Y X X  [0,T] [0, T], [2,T]
        X Y Y  [1,T] [0, T] [1, T]
        X Y Y  [2,T] [0, T] [0, T]
        '''
        def getVal(ch):
            if ch == 'X':
                return [1,True]
            elif ch == 'Y':
                return [-1, False]
            return [0, False]


        dp = [[[None, None] for _ in range(n)] for _ in range(m)]
        dp[0][0] = getVal(grid[0][0])
        count = 0
        for j in range(1,n):
            val = getVal(grid[0][j])
            dp[0][j][0] = val[0] + dp[0][j-1][0]
            dp[0][j][1] = val[1] or dp[0][j-1][1]
            if dp[0][j] == [0, True]:
                count += 1
                
        for i in range(1,m):
            val = getVal(grid[i][0])
            dp[i][0][0] = val[0] + dp[i-1][0][0]
            dp[i][0][1] = val[1] or dp[i-1][0][1]
            if dp[i][0] == [0, True]:
                count += 1

        for i in range(1,m):
            for j in range(1,n):
                val = getVal(grid[i][j])
                dp[i][j][0] = dp[i-1][j][0] + dp[i][j-1][0] + val[0] - dp[i-1][j-1][0]
                dp[i][j][1] = dp[i-1][j][1] or dp[i][j-1][1] or val[1]
                if dp[i][j] == [0, True]:
                    count += 1
        return count

        
129098