Overview

Given an \(H \times W\) seating chart, a seat is considered a “unique seat” if its character appears only once in its row and only once in its column. The task is to concatenate the characters of all unique seats in row-major order (left to right, top to bottom) and output the result.

Analysis

Key Insight

For a seat \((i, j)\) to be unique, the following two conditions must be satisfied simultaneously:

1. The character \(G_{i,j}\) appears only once in row \(i\)
2. The character \(G_{i,j}\) appears only once in column \(j\)

For example, consider the following \(3 \times 3\) seating chart:

abc
bca
cab

The character at seat \((1, 1)\) is a. In row 1 abc, a appears only once, and in column 1 (from top: a, b, c), a also appears only once, so it is unique.

Problem with the Naive Approach

If for each seat \((i, j)\) we scan the entire row and entire column every time to count occurrences, it costs \(O(H + W)\) per seat, resulting in \(O(H \times W \times (H + W))\) overall. When \(H, W\) are up to \(1000\), this amounts to roughly \(2 \times 10^9\) operations, which risks TLE.

Solution

By preprocessing the character occurrence counts for each row and each column in advance, we can determine whether each seat is unique in \(O(1)\).

Algorithm

1. Compute character occurrence counts per row: For each row \(i\), use a Counter to record how many times each character appears. Store this as row_count[i].

2. Compute character occurrence counts per column: For each column \(j\), scan all rows to record how many times each character appears. Store this as col_count[j].

3. Uniqueness check: For seat \((i, j)\), if character \(c = G_{i,j}\) satisfies row_count[i][c] == 1 and col_count[j][c] == 1, then it is a unique seat.

4. Output the result: Concatenate the characters of unique seats in order from left to right in row 1, then left to right in row 2, and so on, then output.

Complexity

• Time complexity: \(O(H \times W)\)
  • Row counting: Scanning each row’s string totals \(O(H \times W)\)
  • Column counting: Scanning all seats totals \(O(H \times W)\)
  • Uniqueness check: Scanning all seats with \(O(1)\) per seat totals \(O(H \times W)\)
• Space complexity: \(O(H \times W + (H + W) \times |\Sigma|)\)
  • \(|\Sigma| = 26\) (number of lowercase alphabet characters)
  • \(O(H \times W)\) for storing the seating chart, \(O((H + W) \times 26)\) for storing the counters

Implementation Notes

• Using Python’s collections.Counter, you can easily obtain the occurrence count of each character by simply passing the string directly.

• Column-wise counts can be computed by iterating through rows and incrementing each column’s counter as you go (there is no need to construct a string for each column).

• By using sys.stdin.buffer.read() to read all input at once, even large inputs can be processed efficiently.

  Source Code

import sys
from collections import Counter

def main():
    input_data = sys.stdin.buffer.read().decode()
    tokens = input_data.split()
    idx = 0
    H = int(tokens[idx]); idx += 1
    W = int(tokens[idx]); idx += 1
    
    grid = []
    for i in range(H):
        grid.append(tokens[idx]); idx += 1
    
    # Count occurrences of each character in each row
    row_count = []
    for i in range(H):
        row_count.append(Counter(grid[i]))
    
    # Count occurrences of each character in each column
    col_count = [Counter() for _ in range(W)]
    for i in range(H):
        for j in range(W):
            col_count[j][grid[i][j]] += 1
    
    result = []
    for i in range(H):
        for j in range(W):
            c = grid[i][j]
            if row_count[i][c] == 1 and col_count[j][c] == 1:
                result.append(c)
    
    print(''.join(result))

main()

---

This editorial was generated by claude4.6opus-thinking.