Overview

This problem asks you to collect characters from each cell that “appear only once in both its row and its column,” scanning from the top-left in row-major order, and output the concatenated string.

Analysis

The condition for a seat \((i,j)\) to be unique is that both of the following hold simultaneously:

• The character \(G_{i,j}\) appears exactly \(1\) time in row \(i\)
• The character \(G_{i,j}\) appears exactly \(1\) time in column \(j\)

In other words, we can determine this if we know “whether the occurrence count of that character is 1 in both its row and its column.”

A naive approach of checking for each cell: - Scanning the entire row to count how many times the same character appears (\(O(W)\)) - Scanning the entire column to count how many times the same character appears (\(O(H)\))

would cost \(O(H+W)\) per cell, resulting in \(O(HW(H+W))\) overall, which is too slow for the maximum case of \(1000 \times 1000\).

Instead, we precompute: - The occurrence count of each character (a–z) for each row - The occurrence count of each character (a–z) for each column

Then, for each cell, we check the precomputed results in \(O(1)\). Since there are only 26 lowercase letters, the aggregation is also fast.

Algorithm

1. Read the input grid (\(H\) rows of strings).
2. Prepare arrays of size \(H \times 26\) and \(W \times 26\), where row_cnt[i][c] is “the occurrence count of character \(c\) in row \(i\)” and col_cnt[j][c] is “the occurrence count of character \(c\) in column \(j\)”.
3. Scan all cells \((i,j)\) once, and for each character ch:
   • row_cnt[i][ch] += 1
   • col_cnt[j][ch] += 1 to aggregate the occurrence counts.
4. Scan all cells again from the top-left in row-major order, and for each cell \((i,j)\) with character ch:
   • If row_cnt[i][ch] == 1 and col_cnt[j][ch] == 1, append it to the answer.
5. Concatenate the appended characters and output them (if there are none, output an empty line).

(Example) If the same character appears twice in a row, that character in that row will be rejected by the “row condition” regardless of which column it is in, so precomputing the counts is effective.

Complexity

• Time complexity: \(O(HW)\)
  (Just two passes over the grid: one for aggregation and one for checking)
• Space complexity: \(O((H+W)\cdot 26)\)
  (26-character counts for each row and column, plus \(O(HW)\) to store the input grid)

Implementation Tips

• Converting character ch to 0–25 and managing it with arrays is fast (k = ord(ch) - ord('a')).

• For output, it is efficient to append characters to a list and then use "".join(...) at the end (repeated string concatenation tends to be slow).

• Even when there are 0 unique seats, the problem requires “outputting an empty line,” so make sure to always include "\n" at the end of the output.

  Source Code

import sys

def main():
    input = sys.stdin.buffer.readline
    H, W = map(int, input().split())
    grid = [input().decode().strip() for _ in range(H)]

    row_cnt = [[0] * 26 for _ in range(H)]
    col_cnt = [[0] * 26 for _ in range(W)]

    for i in range(H):
        row = grid[i]
        rc = row_cnt[i]
        for j, ch in enumerate(row):
            k = ord(ch) - 97
            rc[k] += 1
            col_cnt[j][k] += 1

    out = []
    for i in range(H):
        row = grid[i]
        rc = row_cnt[i]
        for j, ch in enumerate(row):
            k = ord(ch) - 97
            if rc[k] == 1 and col_cnt[j][k] == 1:
                out.append(ch)

    sys.stdout.write("".join(out) + "\n")

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.