Check Div1-500 here.

It can be solved in linear time using Z-Function.

If you have an index i such that Z[i] >= i, this means that the third pattern YYW occurs and the second Y starts at that index. Similarly, if i + Z[i] == string.size(), there is a suffix starts at index i that matches a prefix, which is the second pattern YXY. The first pattern is similar to the third one. Just reverse the string and do the same. Also don't forget to handle the "non-empty" condition.

Here is my code.

You can extract the 3rd parameter from the first two to get O(N ^ 2) solution.

formula: col2 = ((remainingRows * 2) — col1) / 2;

• Binary search the lower bound of the minimum sum of the 16 sub-rectangles
• brute force the 3 vertical cuts
• greedily pick the horizontal cuts in order to exceed the lower bound
• total complexity O(n^4 log n) .. using pre-calculated partial 2D sums