I still don't understand
I'm not too familiar with DP. What does 'i' symbolize? What does the above line mean? Why is the range ~= max_number_of_strings * max_length_of_strings?
I briefly thought about some kind of sorting but then I didn't know how to handle when certain items needed to be left out.

The i is the loop variable. I think the best way to show what this memo (memoization table) does is with an example:

Let's say the input we're given are the following:

(((...( [250 ('s, so the balance is +250, and the size is 250]
(((...()...) [200 ('s, followed by 50 )'s, balance +150, size 250]
(((...( [150 ('s, balance +150, size 150]

These are in sorted order as well, and for now to keep things simple we are not considering offset parentheses chunks (so all 3 of the chunks above have an offset value of 0). We have nothing right now, and for our first chunk, memo[chunk.balance] == memo[250] == 0, so we go ahead and add the first chunk to the memo table (memo[250] = 250):

What this tells us is that the best choice (based on size) for any combination of chunks (here we just have 1 chunk) that has a balance of +250 has a size of 250. Right now we're just dealing with the positive memo table; if our negative memo table also had a value greater than 0 in index 250, then the answer would be that value + 250 (e.g., if we had processed ()))...) [1 ( and 251 )'s, or a balance of -250 and size 252], the negative memo table would have a value of 252 in index 250, then our answer would be 250 + 252 = 502).

Anyways, so the next chunk we have is (((...()...) [200 ('s, followed by 50 )'s, balance +150, size 250]. We iterate through the memo table from the end and any time we find a value > 0 at index i, we check to see if it's worth adding this chunk or not. That's this part of the code:

In this case we definitely should, because memo[250 + 150] == memo[400] == 0. And like the first time, we check memo[chunk.balance] as well (which also == 0, so we update that too) so now our memo table looks like this:

You can start to see why the memo table needs to be as large as 300 * 300 now, right? We're only 2 chunks in and we're already up to index 400 (could have gone up to 600 at this point, or 300 * 2, and we can have up to 300 chunks).

Now for the last chunk (((...( [150 ('s, balance +150, size 150]. First index we hit since we're going from the end is i = 400. memo[i + chunk.balance] == memo[400 + 150] == memo[550] == 0, so that's updated to 500 + 150 = 650. But now, when we hit the next index i = 250, we see that memo[i + chunk.balance] == memo[250 + 150] == memo[400] == 500. In this case,
So this time we don't use the chunk. What does this mean? For sake of simplicity, let's say the only chunks we have that are negatively balanced are ))...) [200 )'s] and ))...) [200 )'s again], so we know the negative memo table's value at index 400 is 400. Look again at the choices we have for our positively balanced chunks. Clearly, it is better to utilize only the first two chunks (for a total size of 500 + 400 = 900) and not bother with the third (for a total size of (250 + 150) + 400 = 800 < 900), and that's what this memo table is tracking for us. So at index 400, we keep what we have, and the same goes for index 150 (why use the 3rd chunk when the 2nd chunk has the same positive balance but greater size?).

Sorry this got so long-winded, but that's essentially what this memoized table is doing for us. It's "standard" DP in the sense that this is almost exactly the technique used in solving problems like the Coin Change problem, a classical DP problem.

Indeed, but when I tried something far simpler like:
It would pass the first 3 test cases, before hitting TLE on the fourth (I wrote the C++ equivalent, and found it would hit TLE even sooner, at the second test case).

How is it guaranteed that we'll use a piece only once?
Say our test case is: '(', '(', ')', ')' then our positive memo table will be [0, 1, 2] and our negative memo table the same,
so when we compare memo table entries we will add 4 for i==2 which is correct, but then we'll add 2 for i==1 resulting in a sum of 6 which is incorrect.

Once we've calculated the memo tables, the dynamic programming step is done! As we're stepping through the memo tables and find cases where there are positive values in the same index across the tables, we're just trying to find the max (and we're going through them in regular order). So at i=1, we see values 1 and 1 across the tables, add them, and set that as our current max. Then at i=2, we see values 2 and 2 across the tables, add them, see that this value is higher, and set that as our new max, which is our answer.

Well, you're not in control of whether the library uses a clever algorithm. I had a look at libstdc++ and it looks like it doesn't (there's a mention of KMP only for a parallel version string search, the default seems to be the naive loop).
I've built a KMP version with a slightly different approach. I think you can just compute the solution while building the kmp prefix table: whenever the length of the prefix is equal to the length of the original string, you've found S within S+S. The first time this occurs, you can stop searching. As an additional optimization you can avoid the string copy by just noticing when your index goes past the length and wrapping it. I implemented this without reference to your program, just looking at general KMP algorithm descriptions elsewhere, and I suspect that this version would be good for spot 2 on the performance leaderboard (assuming it really works). Would you object if I submitted it?
I suspect Bill's method could very slightly improve runtimes further in some cases, but the solution is already linear and that obviously won't change, so I imagine the improvement would be very limited.

Go for it! I'm curious .

My aim is to find n without doing any substring matches. (OC, you have to check it. Unless it is 1, which I doubt.) Suppose that n is odd. Then the probability of any character count being even is 0.5, assuming independence, which is a maybe. The probability of all 26 character counts being even is 0.5^26. Well, there are 223 primes less than √2,000,000, so there is a chance that one of them will divide all of the character counts but not n. However, throw in 676 possible digrams and I think that the chances of finding n via the GCD are damn good.

Oddly, even after throwing a few more optimizations at it, Kattis reports a longer run-time than it does for my earlier version that does factorization. I'm somewhat surprised: it's got a linear algorithm, I don't have to precompute a big table of prime numbers for every invocation, it should be faster - right? Maybe the extra KMP table blows out the cache; there may be a lesson here.