Overview

Given a seating chart of \(H\) rows and \(W\) columns, the problem asks you to find all “unique seats” — seats where the class name (character) appears only once in its entire row and only once in its entire column — then concatenate them in scanning order and output the result.

Analysis

The most important aspect of solving this problem is efficiently determining whether a given seat \((i, j)\) is unique.

Naive Approach (Too Slow)

For every seat \((i, j)\), we could check each time whether “the same character exists elsewhere in the same row” and “the same character exists elsewhere in the same column.” - Checking a single seat takes \(O(H + W)\). - There are \(H \times W\) seats in total. - The overall time complexity is \(O(HW(H+W))\).

Given the constraints \(H, W \leq 1000\), this requires up to \(1000 \times 1000 \times 2000 = 2 \times 10^9\) operations, which will not fit within the time limit (typically about 2 seconds).

Efficient Approach

We can speed up the checks by precomputing the occurrence count of each character in every row and every column. - row_counts[i][character] : the number of occurrences of that character in row \(i\) - col_counts[j][character] : the number of occurrences of that character in column \(j\)

With these precomputed, for a seat \((i, j)\) with character \(c\), we can determine in \(O(1)\) that it is unique if and only if row_counts[i][c] == 1 and col_counts[j][c] == 1.

Algorithm

The problem can be solved with the following steps:

1. Count occurrences: Scan the entire seating chart once and create arrays (or associative arrays) recording how many times each letter ‘a’–’z’ appears in each row and each column.
2. Extract unique seats: Scan the seating chart from the top-left corner (left to right in row 1, then row 2, and so on). For the character \(G_{i,j}\) at each seat \((i, j)\), check the following conditions:
   • The occurrence count of \(G_{i,j}\) in row \(i\) is 1.
   • The occurrence count of \(G_{i,j}\) in column \(j\) is 1.
3. Output: Concatenate the characters of seats that satisfy the conditions in order and output the resulting string.

Complexity

• Time complexity: \(O(HW)\)
  • Scanning the seating chart (twice: once for counting and once for checking) takes \(O(HW)\). The number of alphabet types (26) can be treated as a constant. When \(H, W = 1000\), \(HW = 10^6\), which is sufficiently fast.
• Space complexity: \(O(HW)\)
  • Storing the seating chart requires \(O(HW)\) memory, and storing the occurrence counts requires \(O(26(H+W))\) memory.

Implementation Tips

• Converting characters to numbers: By converting characters to numbers 0–25 using something like ord(c) - ord('a') and using them as array indices, the counting process becomes straightforward.

• Fast I/O: Since \(H\) and \(W\) can be large, in Python you can reduce execution time by reading all input at once using sys.stdin.read().split() or similar methods.

• Handling empty strings: Be careful to output an empty string (or an empty line) when no unique seats exist. Using the join method handles empty lists gracefully, producing an empty string appropriately.

  Source Code

import sys

def solve():
    # 入力を一括で読み込み、空白文字（スペース、タブ、改行）で分割します。
    # これにより、H, W と座席表の各行を柔軟に取得できます。
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
        
    if len(input_data) < 2:
        return
    
    try:
        H = int(input_data[0])
        W = int(input_data[1])
    except (ValueError, IndexError):
        return
    
    # 座席表の文字データを1つの文字列に連結し、H行W列の形式に再構成します。
    # 各行の文字列内にスペースが含まれている場合でも、これで正しく処理できます。
    all_grid_chars = "".join(input_data[2:])
    G = [all_grid_chars[i*W : (i+1)*W] for i in range(H)]
    
    if not G:
        if H > 0:
            sys.stdout.write("\n")
        return

    # 各座席のクラス名をアルファベットのインデックス（0-25）に変換しておきます。
    # これにより、ループ内での ord() 呼び出しを減らし高速化を図ります。
    G_idx = [[ord(c) - 97 for c in row] for row in G]
    
    # row_counts[i][c]: 第 i 行におけるクラス名（インデックス c）の出現回数
    # col_counts[j][c]: 第 j 列におけるクラス名（インデックス c）の出現回数
    row_counts = [[0] * 26 for _ in range(H)]
    col_counts = [[0] * 26 for _ in range(W)]
    
    # 全ての座席を走査し、各行および各列における各クラス名の出現回数をカウントします。
    for i in range(len(G_idx)):
        row_i_idx = G_idx[i]
        row_counts_i = row_counts[i]
        for j in range(len(row_i_idx)):
            c_idx = row_i_idx[j]
            # 行ごとのカウント
            row_counts_i[c_idx] += 1
            # 列ごとのカウント（jがWの範囲内であることを確認）
            if j < W:
                col_counts[j][c_idx] += 1
    
    unique_chars = []
    # 座席表を左上から行ごとに走査し、「ユニークな座席」の条件を満たすか判定します。
    for i in range(len(G_idx)):
        row_i_idx = G_idx[i]
        row_counts_i = row_counts[i]
        row_i_str = G[i]
        for j in range(len(row_i_idx)):
            c_idx = row_i_idx[j]
            if j < W:
                # 条件: その行で唯一かつ、その列で唯一のクラス名であること
                if row_counts_i[c_idx] == 1 and col_counts[j][c_idx] == 1:
                    unique_chars.append(row_i_str[j])
    
    # 見つかったユニークな座席のクラス名を連結して出力します。
    # ユニークな座席がない場合は空行が出力されます。
    sys.stdout.write("".join(unique_chars) + "\n")

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.