Count Cells in Overlapping Horizontal and Vertical Substrings

Count Cells in Overlapping Horizontal and Vertical Substrings

What is this problem about?

The Count Cells in Overlapping Horizontal and Vertical Substrings interview question involves a 2D grid of characters. You are given a target string P. You need to count how many cells (r, c) in the grid are part of at least one horizontal occurrence of P AND at least one vertical occurrence of P.

Why is this asked in interviews?

Google asks this Matrix interview pattern to evaluate your string matching and grid traversal efficiency. It’s a "Medium" problem because you must avoid redundant checks. It tests whether you can use boolean matrices to mark "covered" cells and whether you can efficiently find occurrences of a pattern in both rows and columns.

Algorithmic pattern used

The problem uses String Matching (KMP or Rolling Hash) and Matrix Marking.

1. Initialize two boolean matrices: horizontal_covered and vertical_covered.
2. For each row, use a string matching algorithm (like indexOf or KMP) to find all occurrences of P. Mark all cells in those occurrences in horizontal_covered.
3. For each column, do the same for vertical_covered.
4. The answer is the count of cells where horizontal_covered[r][c] and vertical_covered[r][c] are both true.

Example explanation

Grid: A B A B A B A B A Pattern P = "ABA"

1. Row 0: ABA found. Mark (0,0), (0,1), (0,2) in H_map.
2. Row 2: ABA found. Mark (2,0), (2,1), (2,2) in H_map.
3. Column 0: ABA found. Mark (0,0), (1,0), (2,0) in V_map.
4. Column 2: ABA found. Mark (0,2), (1,2), (2,2) in V_map. Overlapping cells: (0,0), (0,2), (2,0), (2,2). Result: 4.

Common mistakes candidates make

• Overcounting: Counting the same cell multiple times if it belongs to two different horizontal occurrences.
• Efficiency: Using a naive string search in every row and column, which might be slow if the pattern is long.
• Column Extraction: Not extracting columns efficiently for string matching, which can lead to excessive memory copies.

Interview preparation tip

When working with grid patterns, always think about "Marking." Instead of calculating complex overlaps, use a simple boolean array to track which cells meet each individual condition.