Similar to what peti said about Problem C: I've made so much incremental progress in formulating it as a DP problem, but still I'm running out of time at test case 34 ...

Problem B: after my initial naive approach I decided to cut the string to n pieces (n going 2,3,4,5...) and see if the pieces are identical. If yes, take the piece, drop everything else and start again. At the end multiply the result according to the pieces dropped (i.e.: if I find that cutting to 3 works and then cutting that 1/3 to 2 pieces again works, the multiplier is 6).
What was the final realization for me is that I only needed to check for prime number n-s (as there is no way a string can have 4 repetition when there is no 2). This I found a bit absurd because there is knowingly no quick way to check for primes. Still my clumsy naive implementation of prime number checking yielded the key to solve this problem.

Problem C: at first I implemented a huge recursive multi level loop to evaluate every permutation (so that order matters) of selected k items (where k is 1 to count of all items). The "))((" test case item really freaked me out and I'm so glad that it was among the examples.
Then later I came up with a formula that allowed me to verify a set of selected k items without trying all the permutations but I still needed to try out all possible sets of k items (where k is 1 to count of all items).
I then added a few optimizations (e.g. going with k from count of all items down to 1 and exiting if for whatever k I found a working set). I also noticed that I can freely drop items that (evaluating from left to right) never have fewer '('-s than ')'-s and have equal number of '('-s and ')'-s as I can always append them without ruining the balance. So I dropped them and added their length to the solution.
But then I was still running out of time on test case 3. I added a few more early checks (return 0 if every item has more '('-s than ')'-s or the other way around), improved my naive "get k of n in every permutation" loop, but then I ran out of ideas. The .net fiddle page started freezing on me, and it was 2:30AM so I called it a day, but I'm very curious what I could have missed.

There's a well-known algorithm to generate a list of primes in advance.

My optimization was to factor the length of the input string and then only check substrings that were equal in length to one of the factors. I didn't check in advance, but the maximum number of factors of a number n can be given by the equation 2**(1.5379 * (log(n)/log(log(n)))), which comes out to a max of 4457 factors at the test case limit of 2 million. The average case will be smaller, but even in the worst case that's not too many cases to check in the allotted time.

Like peti29, I implemented a recursive backtracking solution that worked on small data sets but didn't handle the test input. That's actually not surprising.
A lot of problems in programming competitions like this seem like they can be solved with backtracking, but that is almost always the wrong approach. Backtracking is generally O(n!), which blows up the problem space very, very quickly unless you can find a way to severely prune the search tree. I could prune the tree significantly for the average case, but I'm sure the test cases included adversarial input designed to foil most common pruning strategies.

I suspect that there is a numeric solution that doesn't involve ordering the strings at all. I have some idea of the proper data representation (all you need to know about each string is the number of unmatched open parentheses, the number of unmatched closed parentheses, and the length of the string), and some important simplifications (the total number of open and closed parentheses must match, any substrings that consist of matched parentheses can add their length to the solution without further impacting the search space), but I never had the flash of insight that usually accompanies the discovery of the proper algorithm.

How to limit the size of n?

The following assumes that the whole string has been read and that an array or arrays or a dictionary is used.

Let Length be the length of the string. Length mod n = 0.

Let Count(char) be the number of occurrences of char in the string. For each character, Count(char) mod n = 0.

That means that we may be able to use the Greatest Common Denominator (GCD) to limit the size of n before matching substrings. We have

n(max) = GCD(Count(“a”), Count(“b”), . . . , Count(“z”))

Since Length = ∑ Count, we can replace one of the Counts with Length. For instance, if Length is a prime, we know that n(max) is Length or 1, but if we only look at the Counts, we may not realize that for some time. For instance, with Length = 7, the Counts (leaving out 0s) might be (2,2,3).

It is a good idea, I think, to sort the Counts and start with the minimum non-zero Count to find the GCD.

Let’s apply all this to the example strings.

String = “abcd”
Length = 4
Count(”a”) = 1
n(max) = GCD(1,4) = 1
n = 1

String = “aaaa”
Length = 4
Count(“a”) = 4
n(max) = GCD(4,4) = 4

String = “ababab”
Length = 6
Count(“a”) = 3
n(max) = GCD(3,6) = 3 ; Note that we do not need to check Count(“b”). It is redundant.

In the next example, let’s just use the numbers.

Length = 48
Count(“a”) = 18
Count(“b”) = 30
n(max) = GCD(18,48) = 6 ; Again, we do not have to make use of Count(“b”).

Can we also make use the number of occurrences of digrams? With a possible Length of 2,000,000 that might help. The answer is yes, with a twist. Let’s look at the last example:

String = “ababab”

Count(“ba”) = 2
Count(“ab”) = 3
n(max) = GCD(2,3) = 1

This is plainly wrong. We cannot use the GCD of the number of occurrences of “ab” and “ba”. The reason is that “ba” does not belong to the repeating substring. The “b” belongs to one substring while the “a” belongs to the next substring. In fact, in this case Count(“ba”) = n-1. It could also equal the count of “ba” in the repeating substring plus n-1. In either case, if we add 1 to it, we can use it, as adding n to a count does no harm. Let’s do that.

GCD(inc(2),3) = 3

So far, so good. But how do we do know whether to add 1 to Count(“ab”) or to Count(“ba”)? Easy. “a” is the first letter in String, and “b” is the last letter. That tells us that “ba” marks the boundaries between repeating substrings.

Now, when we use digrams, we add 1 to the Count of the digram whose first character is the last character in String and whose second character is the first character in String. When we do that, the sum of the counts = Length, as it should.

In this case the digrams give us no reduction of n(max) from the result we get using single letters.

But let’s look at this example:

String = “abbaab”

Using single characters:

Count(“a”) = 3
Count(“b”) = 3
n(max) = GCD(3,3) = 3

Using digrams:

The sorted Counts:

Count(“aa”) = 1
Count(“bb”) = 1
Count(“ba”) = 1
Count(“ab”) = 2

n(max) = GCD(1,1,2,2)) = 1 ; We add 1 to Count(“ba”)
n = 1

OC, in this case we do not have to make the full computation. In fact, since Count(“bb”) = 1, we don’t need to calculate any GCD at all.

Note that even if we get a lower limit for n with the digrams than we do with the single character counts, we may be able to use the single character count result to reduce the limit even further. It does not hurt to start with the single character counts.

String = “abaabababaabacbabaababababaacb”
Length = 30 ; Chosen because of its number of divisors

Count(“c”) = 2
Count(“b”) = 12
Count(“a”) = 16
n(max) = GCD(2,12,16) = 2

Count(“ac”) = 2
Count(“cb”) = 2
Count(“aa”) = 4
Count(“ab”) = 10
Count(“ba”) = 11 ; Add 1 to this

n(max) = GCD(2,2,4,10,12) = 2

This example is meant to illustrate the virtue (I hope) of this approach. The string is perhaps deceptive in part because of so many repetitions of the initial and final parts of the string (the “a”s and “b”s). That means that if we are working down the candidate substrings, we will get early matches, whether we work from the front or the back. There are also a lot of potential “ba” boundaries between substrings. But that means that there are a lot of “a”s and “b”s, but relatively few “c”s. It is the paucity of “c”s that puts a cap on n. With only 2 “c”s n(max) = 2, while using the counts of only “a” and “b” gives us an n(max) of 4.

OC, as always, the proof is in the pudding.

The way I approached this problem was to utilize the preprocessing function from the KMP algorithm (call it kmp_pre). Specifically, the function calculates for every index of a pattern P, the length of the longest border (substring that is both a prefix and a suffix) found up to that index. For example, kmp_pre('aabbaabb') = [0 1 0 0 1 2 3 4], and kmp_pre('ababab') = [0 0 1 2 3 4].

If however, instead of running kmp_pre on P, we run it on P + P, then the border length found at an index equal to the size of P tells us the length of the period len(period) := i - kmp_pre[i] + 1, and the value of n from the problem statement would just be len(P) / len(period). A way of visualizing this is to imagine P on two pieces of tape, and you're trying to align them such that the borders align, the length of the gap ('<>') on the left telling you the length of 'a' in the problem statement (s = a^n):

Example 1: let P = aabbaabb => len(P) = 8. Then kmp_pre(P + P) = [0 1 0 0 1 2 3 4 5 6 7 8 9 10 11 12]. At i = 11, the border length of P + P == 8, i.e, that aabbaabbaabb = P + aabb has a substring of length 8 that is both a prefix and a suffix (P), so len(a) = 11 - 8 + 1 = 4. Then n = len(P) / len(a) = 8 / 4 = 2.

Example 2: let P = ababab => len(P) = 6. Then kmp_pre(P + P) = [0 0 1 2 3 4 5 6 7 8 9 10]. At i = 7, the border length of P + P == 6, so len(a) = 7 - 6 + 1 = 2. Then n = len(P) / len(a) = 6 / 2 = 3.

Example 3: let P = abcd => len(P) = 4. Then kmp_pre(P + P) = [0 0 0 0 1 2 3 4]. At i = 7, the border length of P + P == 4, so len(a) = 7 - 4 + 1 = 4. Then n = len(P) / len(a) = 4 / 4 = 1.

Intuitively I knew this was a DP problem, but problem was getting the state and the transition correct. For the state, several pieces of information is necessary. Start with size and balance...

• size: just the length of the string
• balance: counter to keep track of difference between number of ('s vs )'s. e.g., ()()()'s balance = 0, ((('s balance = 3, ()(())(('s balance = 2.

If we utilized just these two pieces of information and ran DP with it, that would be ideal, and it would handle a lot of cases like ['(((', ')))'] or ['(())((', ')))', '(()', '(((())']. However, what this doesn't handle is differentiating between something like (()) versus ))((, both of which would have a balance of 0 and same size, but clearly must be handled differently (the first case is "free", the second one not so much...). So a third piece of information (call it 'offset') is needed, which is always <= 0 and counts the number of )'s that come before a positively balanced chunk, or the number of ('s that come after a negatively balanced chunk. So (()) would have an offset of 0, but ))(( would have an offset of -2. It's worth noting that if we are only dealt chunks with negative offsets, then we can't merge any chunks together. In the case of ))((, we would need something (one of many examples) like (( (balance +2, offset 0) and )) (balance -2, offset 0) to merge with. Hence, when we sort these chunks, we need to sort by offset (descending) first to find the ones with 0 offset, before looking balance and size.

That's pretty much the hard part, the DP is simpler:
We keep track of two memo tables: one for positively balanced chunks, one for negatively balanced chunks. After that, we go through the memo tables and find the highest aligned value between them, and that's the answer.

This is just equivalent to searching for S withing S+S (and ignoring the first match), right? I get the feeling this is how it was intended to be solved. I just went with the factorization. The interesting thing is that your solution looks like it should be more efficient, but runs slightly slower in practice in my tests. This is something I'll probably spend time on to try to understand - is C++ string handling that inefficient?

Yes, that matches what I did. I found that if I sort this data correctly, I can just run the DP algorithm over all of it once and get the right answer at the end.

It's relatively simple to write a recursive algorithm to generate an alphabetical sequence that matches the requirements. You have to keep track of what the previous character was, and how many characters have been used i times for 1 <= i <= k (and set limits as appropriate).
My first attempt at speeding it up was to recognize that the fact that we're duplicating a lot of patterns if we're going through the whole alphabet. If at any point we're choosing a new character that hasn't been seen before, we can remember how many substrings the recursive calls generated, and then any other choice of new characters will generate the same number. As long as that number is smaller than the remaining count, we can skip the recursive call and just subtract.
This turns out to work great for small k such as in the examples, where we always choose many different new characters, but for large k (approaching 26) it becomes less effective, and here we need speedups the most. So in the end I didn't end up using this. Instead, I recognize when the subproblem becomes suitably small (all character counts above 9 fully used up), and encode the pattern of remaining counts into an index into an array of shortcuts. The idea is the same: if we encounter a similar situation twice, we can skip recursion after the first time.