3529. Count Cells in Overlapping Horizontal and Vertical Substrings Medium

1/**
2 * [3529] Count Cells in Overlapping Horizontal and Vertical Substrings
3 *
4 * You are given an m x n matrix grid consisting of characters and a string pattern.
5 * A <strong data-end="264" data-start="240">horizontal substring is a contiguous sequence of characters read from left to right. If the end of a row is reached before the substring is complete, it wraps to the first column of the next row and continues as needed. You do not wrap from the bottom row back to the top.
6 * A <strong data-end="484" data-start="462">vertical substring is a contiguous sequence of characters read from top to bottom. If the bottom of a column is reached before the substring is complete, it wraps to the first row of the next column and continues as needed. You do not wrap from the last column back to the first.
7 * Count the number of cells in the matrix that satisfy the following condition:
8 * 
9 * 	The cell must be part of at least one horizontal substring and at least one vertical substring, where both substrings are equal to the given pattern.
10 * 
11 * Return the count of these cells.
12 *  
13 * <strong class="example">Example 1:
14 * <img alt="" src="https://assets.leetcode.com/uploads/2025/03/03/gridtwosubstringsdrawio.png" style="width: 150px; height: 187px;" />
15 * <div class="example-block">
16 * Input: <span class="example-io">grid = [["a","a","c","c"],["b","b","b","c"],["a","a","b","a"],["c","a","a","c"],["a","a","b","a"]], pattern = "abaca"</span>
17 * Output: <span class="example-io">1</span>
18 * Explanation:
19 * The pattern "abaca" appears once as a horizontal substring (colored blue) and once as a vertical substring (colored red), intersecting at one cell (colored purple).
20 * </div>
21 * <strong class="example">Example 2:
22 * <img alt="" src="https://assets.leetcode.com/uploads/2025/03/03/gridexample2fixeddrawio.png" style="width: 150px; height: 150px;" />
23 * <div class="example-block">
24 * Input: <span class="example-io">grid = [["c","a","a","a"],["a","a","b","a"],["b","b","a","a"],["a","a","b","a"]], pattern = "aba"</span>
25 * Output: <span class="example-io">4</span>
26 * Explanation:
27 * The cells colored above are all part of at least one horizontal and one vertical substring matching the pattern "aba".
28 * </div>
29 * <strong class="example">Example 3:
30 * <div class="example-block">
31 * Input: <span class="example-io">grid = [["a"]], pattern = "a"</span>
32 * Output: 1
33 * </div>
34 *  
35 * Constraints:
36 * 
37 * 	m == grid.length
38 * 	n == grid[i].length
39 * 	1 <= m, n <= 1000
40 * 	1 <= m * n <= 10^5
41 * 	1 <= pattern.length <= m * n
42 * 	grid and pattern consist of only lowercase English letters.
43 * 
44 */
45pub struct Solution {}
46
47// problem: https://leetcode.com/problems/count-cells-in-overlapping-horizontal-and-vertical-substrings/
48// discuss: https://leetcode.com/problems/count-cells-in-overlapping-horizontal-and-vertical-substrings/discuss/?currentPage=1&orderBy=most_votes&query=
49
50// submission codes start here
51
52impl Solution {
53    pub fn count_cells(grid: Vec<Vec<char>>, pattern: String) -> i32 {
54        0
55    }
56}
57
58// submission codes end
59
60#[cfg(test)]
61mod tests {
62    use super::*;
63
64    #[test]
65    fn test_3529() {
66    }
67}
68