Printing characters in a matrix as a string 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
&gt; 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)
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.