Skip to content

3529. Count Cells in Overlapping Horizontal and Vertical Substrings 👍

  • Time: $O(mn)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
class Solution {
 public:
  int countCells(vector<vector<char>>& grid, string pattern) {
    const int m = grid.size();
    const int n = grid[0].size();
    int ans = 0;
    string flattendGridRow;
    string flattendGridCol;

    // Flatten the grid for horizontal matching.
    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        flattendGridRow += grid[i][j];

    // Flatten the grid for vertical matching.
    for (int j = 0; j < n; ++j)
      for (int i = 0; i < m; ++i)
        flattendGridCol += grid[i][j];

    // Find matching positions.
    const vector<vector<bool>> horizontalMatches =
        markMatchedCells(flattendGridRow, pattern, m, n, true);
    const vector<vector<bool>> verticalMatches =
        markMatchedCells(flattendGridCol, pattern, m, n, false);

    // Count overlapping match positions.
    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (horizontalMatches[i][j] && verticalMatches[i][j])
          ++ans;

    return ans;
  }

 private:
  static constexpr long kBase = 13;
  static constexpr long kHash = 1'000'000'007;

  vector<vector<bool>> markMatchedCells(const string& flattenedGrid,
                                        const string& pattern, int m, int n,
                                        bool isHorizontal) {
    vector<vector<bool>> matchMatrix(m, vector<bool>(n, false));
    vector<int> matchPrefix(flattenedGrid.length() + 1);
    vector<long> pows{1};  // pows[i] := kBase^i % kHash
    long patternHash = 0;
    long runningHash = 0;

    for (int i = 1; i < pattern.length(); ++i)
      pows.push_back((pows.back() * kBase) % kHash);

    for (const char c : pattern)
      patternHash = (patternHash * kBase + (c - 'a')) % kHash;

    for (int i = 0; i < flattenedGrid.length(); ++i) {
      runningHash = (runningHash * kBase + (flattenedGrid[i] - 'a')) % kHash;
      if (i >= pattern.length() - 1) {
        if (runningHash == patternHash) {  // Match found.
          ++matchPrefix[i - pattern.length() + 1];
          --matchPrefix[i + 1];
        }
        // Remove the contribution of the oldest letter.
        const long oldestLetterHash =
            (pows[pattern.length() - 1] *
             (flattenedGrid[i - pattern.length() + 1] - 'a')) %
            kHash;
        runningHash = (runningHash - oldestLetterHash + kHash) % kHash;
      }
    }

    for (int k = 0; k < flattenedGrid.length(); ++k) {
      matchPrefix[k] += (k > 0) ? matchPrefix[k - 1] : 0;
      if (matchPrefix[k] > 0) {
        const int i = isHorizontal ? k / n : k % m;
        const int j = isHorizontal ? k % n : k / m;
        matchMatrix[i][j] = true;
      }
    }

    return matchMatrix;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class Solution {
  public int countCells(char[][] grid, String pattern) {
    final int m = grid.length;
    final int n = grid[0].length;
    int ans = 0;
    StringBuilder flattenedGridRow = new StringBuilder();
    StringBuilder flattenedGridCol = new StringBuilder();

    // Flatten the grid for horizontal matching.
    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        flattenedGridRow.append(grid[i][j]);

    // Flatten the grid for vertical matching.
    for (int j = 0; j < n; ++j)
      for (int i = 0; i < m; ++i)
        flattenedGridCol.append(grid[i][j]);

    // Find matching positions.
    boolean[][] horizontalMatches =
        markMatchedCells(flattenedGridRow.toString(), pattern, m, n, true);
    boolean[][] verticalMatches =
        markMatchedCells(flattenedGridCol.toString(), pattern, m, n, false);

    // Count overlapping match positions.
    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (horizontalMatches[i][j] && verticalMatches[i][j])
          ++ans;

    return ans;
  }

  private static final long BASE = 13;
  private static final long HASH = 1_000_000_007;

  private boolean[][] markMatchedCells(final String flattenedGrid, final String pattern, int m,
                                       int n, boolean isHorizontal) {
    boolean[][] matchMatrix = new boolean[m][n];
    int[] matchPrefix = new int[flattenedGrid.length() + 1];
    long[] pows = new long[pattern.length()]; // pows[i] := BASE^i % HASH
    pows[0] = 1;
    long patternHash = 0;
    long runningHash = 0;

    for (int i = 1; i < pattern.length(); ++i)
      pows[i] = (pows[i - 1] * BASE) % HASH;

    for (final char c : pattern.toCharArray())
      patternHash = (patternHash * BASE + (c - 'a')) % HASH;

    for (int i = 0; i < flattenedGrid.length(); ++i) {
      runningHash = (runningHash * BASE + (flattenedGrid.charAt(i) - 'a')) % HASH;
      if (i >= pattern.length() - 1) {
        if (runningHash == patternHash) { // Match found.
          ++matchPrefix[i - pattern.length() + 1];
          --matchPrefix[i + 1];
        }
        // Remove the contribution of the oldest letter.
        final long oldestLetterHash =
            (pows[pattern.length() - 1] * (flattenedGrid.charAt(i - pattern.length() + 1) - 'a')) %
            HASH;
        runningHash = (runningHash - oldestLetterHash + HASH) % HASH;
      }
    }

    for (int k = 0; k < flattenedGrid.length(); ++k) {
      matchPrefix[k] += (k > 0) ? matchPrefix[k - 1] : 0;
      if (matchPrefix[k] > 0) {
        final int i = isHorizontal ? k / n : k % m;
        final int j = isHorizontal ? k % n : k / m;
        matchMatrix[i][j] = true;
      }
    }

    return matchMatrix;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution:
  def countCells(self, grid: list[list[str]], pattern: str) -> int:
    BASE = 13
    HASH = 1_000_000_007
    m = len(grid)
    n = len(grid[0])

    def markMatchedCells(flattenedGrid: str, isHorizontal: bool) -> list[list[bool]]:
      matchMatrix = [[False] * n for _ in range(m)]
      matchPrefix = [0] * (len(flattenedGrid) + 1)
      pows = [1]  # pows[i] := BASE^i % HASH
      patternHash = 0
      runningHash = 0

      for i in range(1, len(pattern)):
        pows.append((pows[-1] * BASE) % HASH)

      for c in pattern:
        patternHash = (patternHash * BASE + (ord(c) - ord('a'))) % HASH

      for i in range(len(flattenedGrid)):
        runningHash = (
            runningHash * BASE + (ord(flattenedGrid[i]) - ord('a'))) % HASH
        if i >= len(pattern) - 1:
          if runningHash == patternHash:  # Match found.
            matchPrefix[i - len(pattern) + 1] += 1
            matchPrefix[i + 1] -= 1
          # Remove the contribution of the oldest letter.
          oldestLetterHash = (
              pows[len(pattern) - 1] *
              (ord(flattenedGrid[i - len(pattern) + 1]) - ord('a'))) % HASH
          runningHash = (runningHash - oldestLetterHash + HASH) % HASH

      for k in range(len(flattenedGrid)):
        if k > 0:
          matchPrefix[k] += matchPrefix[k - 1]
        if matchPrefix[k] > 0:
          i = k // n if isHorizontal else k % m
          j = k % n if isHorizontal else k // m
          matchMatrix[i][j] = True

      return matchMatrix

    # Find matching positions.
    flattenedGridRow = ''.join(cell for row in grid for cell in row)
    flattenedGridCol = ''.join(cell for col in zip(*grid) for cell in col)
    horizontalMatches = markMatchedCells(flattenedGridRow, True)
    verticalMatches = markMatchedCells(flattenedGridCol, False)
    return sum(horizontalMatches[i][j] and verticalMatches[i][j]
               for i in range(m)
               for j in range(n))