def getOCC(L):
    """
    Returns the OCC data structure such that OCC[c][k] is the number of times char c appeared in L[1], ..., L[k]
    """
    s = set(L)
    d = dict()
    occ = dict()

    for c in set(L):
      d[c] = 0
      occ[c] = [0] * len(L)

    for i in range(len(L)):
      c = L[i]
      d[c] += 1
      for c in set(L):
        occ[c][i] = d[c]

    return occ