Overview

Given an \(H \times W\) seating chart where each seat has an alphabet character written on it, we define a “unique seat” as one whose character (class name) appears exactly once in its row and exactly once in its column. The problem asks us to output the string formed by reading the class names of these seats from top-left to bottom-right.

Analysis

In this problem, for each seat \((i, j)\), we need to determine whether “there is no other occurrence of the same character in that row” AND “there is no other occurrence of the same character in that column.”

A naive approach would be to scan the entire row and column for each seat, counting occurrences of the same character. However, this requires up to \(H + W\) comparisons per seat, resulting in up to \(H \times W \times (H + W)\) total computations. Given the constraints \(H, W \leq 1000\), this could exceed \(2 \times 10^9\) operations in the worst case, which would not finish within the time limit (TLE).

Instead, we precompute the frequency of each character in every row and every column, allowing us to check each seat in constant time. Specifically, for each seat \((i, j)\), we simply verify that the occurrence count of grid[i][j] in row \(i\) and the occurrence count in column \(j\) are both \(1\).

Algorithm

1. For each row, count the occurrences of each character (row_count[i][char]).
2. For each column, count the occurrences of each character (col_count[j][char]).
3. For each seat \((i, j)\), check whether its character char = grid[i][j]:
   • Appears exactly once in row \(i\) (row_count[i][char] == 1)
   • Appears exactly once in column \(j\) (col_count[j][char] == 1) If both conditions are satisfied, the seat is unique.
4. Add the characters of unique seats to a result list in order from top-left to bottom-right, then concatenate and output.

Example

For the following input:

3 3
abc
def
ghi

Every row and every column contains only distinct characters, so all seats are unique. The result is abcdefghi.

On the other hand, for the following input:

2 2
aa
bb

Every seat has a duplicate in its row or column, so there are no unique seats. The result is an empty string.

Complexity

• Time complexity: \(O(H \times W)\)
  • Counting characters for each row and column takes \(O(H \times W)\), and checking each seat takes \(O(H \times W)\).
• Space complexity: \(O(H \times W)\)
  • The memory used by row_count and col_count requires at most \(O(H \times W)\).

Implementation Notes

• The key point is to precompute the character frequency for each row and each column using dictionaries (or similar data structures).

• String concatenation can be done efficiently by using join() only once at the end.

• Don’t forget to handle the case where the output is an empty string (when there are no unique seats).

  Source Code

H, W = map(int, input().split())
grid = [input().strip() for _ in range(H)]

# 各行について、各文字の出現回数をカウント
row_count = [{} for _ in range(H)]
for i in range(H):
    for char in grid[i]:
        row_count[i][char] = row_count[i].get(char, 0) + 1

# 各列について、各文字の出現回数をカウント
col_count = [{} for _ in range(W)]
for j in range(W):
    for i in range(H):
        char = grid[i][j]
        col_count[j][char] = col_count[j].get(char, 0) + 1

# 結果を格納するリスト
result = []

# 各座席についてチェック
for i in range(H):
    for j in range(W):
        char = grid[i][j]
        # 行内でその文字が1回だけ出現し、列内でもその文字が1回だけ出現すればユニーク
        if row_count[i][char] == 1 and col_count[j][char] == 1:
            result.append(char)

print(''.join(result))

This editorial was generated by qwen3-coder-480b.