Finding longest common prefix
Note: although I hinted in a comment that there's a O(n * K) solution, I'm deliberately not going to give it to you (and I hope that by bumping the question to the front page I don't cause someone else to) because in my opinion the point of challenge websites is for you to learn by doing, and you will learn more effectively by figuring it out yourself with hints than by getting the solution on a plate. However, I do have some comments on your code.


class Solution:
    # @param A : list of strings
    # @param B : integer
    # @return an integer



It's useful to document the expected type, but it's more useful to document the meaning. Here B is the K of the problem specification, but I shouldn't have to work that out myself. The parameters would benefit from descriptive names, and the @return should outline what the integer returned means.


    def LCPrefix(self, A, B):
        res = 0
        for i in xrange(len(A)):
            prev = A[i]
            prevLCP = len(A[i])
            for j in xrange(i, len(A)):
                prevLCP = self.getLCP(prev, A[j], prevLCP) 
                prev = A[j]



There's a possible minor optimisation here: when j == i you already know the LCP, but you calculate it again. In my opinion it would be worth duplicating the simple test if prevLCP &gt;= B: res += 1 before the loop, and only considering j &gt; i. As a bonus, you would no longer need to track prev because you would always be testing the common prefix of A[j-1] and A[j]. (Hint: does that give you any ideas for optimisation?)

Why the update to prevLCP? I can figure it out, but a comment (and a better name - because the value of prevLCP isn't the previous LCP) would be useful.


                if prevLCP &gt;= B:
                    res += 1



An else: break clause here would not change the asymptotic complexity of your solution, but it would surely make it much faster in many test cases.


        return res % 1000000007



I'll give you one more hint about improving the complexity: the fact that they want the answer modulo 109 is a really big clue that you shouldn't compute it solely via res += 1.


    def getLCP(self, A, B, upto):



Document the parameters, and think about the names. getLCP implies to me that the return value should be the longest common prefix: i.e. a string. But it's actually an integer, and it might not even be the length of the LCP because of upto.


        i = 0
        lim = min(upto, len(B))
        while i &lt; lim:
            if A[i] != B[i]:
                break

            i += 1

        return i



In the other method you used xrange: why not here?

        lim = min(upto, len(B))
        for i in xrange(lim):
            if A[i] != B[i]:
                return i
        return lim