ARC 071 C - 怪文書 ( Greedy )

C: 怪文書 / Dubious Document - AtCoder Regular Contest 071 | AtCoder

題意：
給 N 個字串，求一個最長的字串，若相同則字典序最小，使得每一個字串都能透過任意刪除、交換位置得到。

制約：
1≤n≤50
i=1,…,n に対して、 1≤|Si|≤50
i=1,…,n に対して、 Si は小文字のアルファベット( a - z )からなる文字列

解法：
對所有字串分別統計每個字符出現幾次，再對每個字符出現次數取最小，最後由字典序最小的字符開始輸出即可。

時間 / 空間複雜度：
O( N * | S | )

N = int( input() )
S = [ input() for i in range( N ) ]
mcnt = [ int( 1e9 ) for i in range( 26 ) ]
for i in range( N ):
  cnt = [ 0 for j in range( 26 ) ]
  for j in range( len( S[ i ] ) ):
    cnt[ ord( S[ i ][ j ] ) - ord( 'a' ) ] += 1
  for j in range( 26 ):
    mcnt[ j ] = min( mcnt[ j ], cnt[ j ] )
ans = ""
for i in range( 26 ):
  if mcnt[ i ] == int( 1e9 ): continue
  for j in range( mcnt[ i ] ):
    ans += chr( ord( 'a' ) + i )
print( ans )