Printing characters in a matrix as a string

Question

I need to solve this problem in Python 3 (within 3 sec):

A is a given (NxM) rectangle, filled with characters "a" to "z". Start from A[1][1] to A[N][M] collect all character which is only one in its row and column, print them as a string.

Input:

\$N\$, \$M\$ in first line (number of row and column \$1 \le N\$, \$M \le > 1000\$). Next, \$N\$ lines contain exactly \$M\$ characters.

Output:

A single string

Sample input 1:

1 9
arigatodl

Sample output 1:

rigtodl

Sample input 2:

5 6
cabboa
kiltik
rdetra
kelrek
dmcdnc

Sample output 2:

codermn

This is still not fast enough when \$N\$, \$M\$ = 1000. I'd like suggestions on improving the speed, or any other ways to solve the given problem, as long as the solution is in Python 3 and is faster than mine.

from operator import itemgetter
Words,Chars,answer=[],"abcdefghijklmnopqrstuvwxyz",""
N,M=[int(i) for i in input().split()]
for _ in range(N):
    Words.append(input())
                                    # got the inputs
for row,word in enumerate(Words):   # going through each words
    Doubts=[]                       # collect chars only one in its row.
    for char in Chars:
            if (word.count(char)==1):
                    Doubts.append((char,word.index(char)))
    for case in sorted(Doubts,key=itemgetter(1)):   #sorting by index
            doubtless=True                  #checking whether 1 in its column or not.
            for i in range(N):
                    if (Words[i][case[1]]==case[0] and i!=row):
                            doubtless=False
                            break
            if (doubtless):
                    answer+=case[0] #if char is one in its row and column, adds to answer.
print (answer)

Answer 1

I would suggest to create a 1000x1000 testcase and measure the performance before the optimization process. Please use the following test generator:

import os
import random

f = open('1000x1000.in','w')
f.write('1000 1000\n')
ALPHABET = 'abcdefghijklmnopqrstuvwxyz'
for _ in range(1000):
       f.write(''.join([ALPHABET[random.randint(0, len(ALPHABET)-1)] for _ in range(1000)]) + '\n')
f.close()

After that just run it and measure the performance of your application. I got about 47 ms on my pretty old C2D E7200.

Answer 2

You could improve part of your loop.

Doubts=[]                     
for char in Chars:
        if (word.count(char)==1):
                Doubts.append((char,word.index(char)))

Can be done with list-comprehension.

    Doubts = [(char, word.index(char)) for char in Chars if word.count(char) == 1]