A. You're Given a String...

The problem asks to find out such a substring that has the longest length and occurs at least two times, which is in fact equivalent to looking for two substrings (they might overlap with each other) with the longest length while they are exactly the same with each other. The solution might be simplified if one has noticed that the string consists of lower-case Lattin letters merely, i.e., a,b,...,z. The idea behind the simplification is that if two substrings are exactly the same, then their first letters must be the same as well. Thus, we can first use 26 arrays to store the positions at which each letter appears. For instance, we can assign 26 vectors (in C++ STL) for each letter, and "puch_back" the corresponding index. This can be done by traversing the string for a single time, with complexity O(N) (we use N to denote the length of string).

For each vector, we enumerate all the feasible combination of two indices (or positions), and start with these two positions and check their next one single letter at the same time. It is obvious that we will obtain two substrings and as we should keep them exactly the same, we must stop if the next one single letter of each substring is different. For instance, suppose that letter "a" has positions {1,5,7}. Then, we should check {1,5}, {1,7} and {5,7}. We adopt {1,7} as an example, i.e., we should check whether the two substrings {s[1],s[2]} and {s[7],s[8]} are the same or not. If they are the same, then we move on to check {s[1],s[2],s[3]} and {s[7],s[8],s[9]}; otherwise, we stop and store the current length. Finally, we output the maximum length as the answer.

Now, we calculate the complexity of the above solution. We denote the length of the 26 vectors as x1,x2,...,x26. For each vector, we should check xi*(xi-1)/2 combinations. For each combination, we will check at most 2N letters. Thus, the total complexity is {x1*(x1-1)/2+x2*(x2-1)/2+...+x26*(x26-1)/2}*2*N=O(N^3).

B. Party

Well, this problem is somewhat marvellous...

We first prove that the answer cannot be n. Note that each person can only have friends with number of 0,1,...,n-1. Therefore, when we count from 0 to n-1, some of them must leave.

Next, we prove that the answer cannot be n-1. Suppose that the person leaves when we count at x. This means that for the "stayed" n-1 people, the number of friends is reduced by one for x of them while nothing changes for the other n-1-x people. Due to similar reasons at the first case, the n-1-x people cannot all stay at the party, which is contradictory to our initial assumption. However, this can be true if and only if n-1-x=0, which gives x=n-1, i.e., the single person leaves when we count at n-1. This implies that the other n-1 people all have friends with number of n-1, since none of them leaves when we count from 0 to n-2. Nevertheless, this also means that when we count at n-1, all the n people will leave, which is contraditory to the initial assumption again.

Thirdly, we prove that the answer is n-2. Actually, the above two cases may have inspired us a little.