0
$\begingroup$

You are given a string s of size n, consisting of characters A and B only. You have to find minimum sum of size of the two disjoint segments of the string s such that number of A's in them are >= z.

Input: string s, n, z are given in the input. Output: minimum sum of size of two disjoint segments with given property

Currently I have a solution of complexity $\mathbf{O}(n^2)$, Can anybody give a better solution than this?

Or can somebody prove that it is somehow related to 3 SUM problem?

Improve this question
$\endgroup$
4
  • $\begingroup$ Discarding Bs in the beginning, we have, say, $x_1$ As, $t_1$ Bs, $x_2$ As, $t_2$ Bs and so on. Let $s_1=x_1$, $s_2=x_1+x_2$, $s_3=x_1+x_2+x_3$ etc., so $0=s_0<s_1<s_2<\cdots$ is arbitrary increasing sequence. We then search for $i<j<k<l$ such that $s_j-s_i+s_l-s_k\geqslant z$, with $j-i+l-k$ as small as possible. With this reformulation, I doubt $O(n^2)$ can be improved. $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Mar 19, 2014 at 10:37
  • 1
    $\begingroup$ Could you please add a more descriptive title? "Another Interesting Maths Problem" could easily refer to any question asked here. $\endgroup$
    – Federico Poloni
    Commented Mar 19, 2014 at 10:46
  • $\begingroup$ ^Federico Poloni, Is it better now? $\endgroup$
    – Praveen Dhinwa
    Commented Mar 19, 2014 at 10:49
  • $\begingroup$ @მამუკა ჯიბლაძე, It seems like $\mathbf{O}(n^2)$ might not be improved, I had the following idea, but still it is not much helpful, Binary search over the length, So given a fixed sum of length, can you find two disjoint segments with given length and having number of A's $\geq$ z. I dont have less than $\mathbf{O}(n^2)$ solution for the subproblem that I mentioned. $\endgroup$
    – Praveen Dhinwa
    Commented Mar 20, 2014 at 13:33

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .