# Given an array A of strings made only from lowercase letters, return a list of all characters that show up in all
# strings within the list (including duplicates).  For example, if a character occurs 3 times in all strings but not
# 4 times, you need to include that character three times in the final answer.
#
# You may return the answer in any order.
#
#
#
# Example 1:
#
# Input: ["bella","label","roller"]
# Output: ["e","l","l"]
# Example 2:
#
# Input: ["cool","lock","cook"]
# Output: ["c","o"]
#
#
# Note:
#
# 1 <= A.length <= 100
# 1 <= A[i].length <= 100
# A[i][j] is a lowercase letter

import collections


class Solution(object):
    # time complexity: O( N * S ) , N : len(A), S = max(len(A[i])), i -> 0..N
    def commonChars(self, A):
        """
        :type A: List[str]
        :rtype: List[str]
        """
        # times : char c in A[i] appears times, positions : char c appears in how many string  in A
        # for test case ["bella","label","roller"]
        # times : [ {'a': 1, 'b': 1, 'e': 1, 'l': 2}),  {'a': 1, 'b': 1, 'e': 1, 'l': 2}),  {'r': 2, 'e': 1, 'l': 2,
        # 'o': 1})]
        # positions : {'a': [0, 1], 'b': [0, 1], 'e': [0, 1, 2], 'l': [0, 1, 2], 'o': [2], 'r': [2]})
        times, postions = [collections.defaultdict(int) for _ in xrange(len(A))], collections.defaultdict(list)
        res = []

        for i in xrange(len(A)):
            for k, v in enumerate(A[i]):
                times[i][v] += 1
                if i not in postions[v]:
                    postions[v].append(i)

        for k, v in postions.iteritems():
            # if char k appears in all strings in A, because its 'v' - pos list has
            # length of len(A), for ex 'l' : [0,1,2], 'e] : [0,1,2]
            if len(v) == len(A):
                # then we get char k, seaerch in every dict in times, find the min value
                # repeat it , add to result
                st = min([t[k] for t in times])
                for i in xrange(st):
                    res.append(k)

        return res


if __name__ == '__main__':
    print Solution().commonChars(["bella", "label", "roller"])
    print Solution().commonChars(["cool", "lock", "cook"])
