CODEWITHSUNDEEP
algorithmmathdata-structures
mtszkw
mtszkw

Reputation: 2783

Find longest positive substrings in binary string

Let's assume I have a string like 100110001010001. I'd like to find such substring that:

So the longest substrings, that have more 1s than 0s.

For example for the string above 100110001010001 it would be: [10011]000[101]000[1]

Actually it's be satisfying to find the total length of those, in this case: 9.

Unfortunately I have no clue, how can it be done not in brute-force way. Any ideas, please?

Upvotes: 5

Views: 425

Answers (2)

גלעד ברקן
גלעד ברקן

Reputation: 23955

As posted now, your question seems a bit unclear. The total length of valid substrings that are "as long as possible" could mean different things: for example, among other options, it could be (1) a list of the longest valid extension to the left of each index (which would allow overlaps in the list), (2) the longest combination of non-overlapping such longest left-extensions, (3) the longest combination of non-overlapping, valid substrings (where each substring is not necessarily the longest possible).

I will outline a method for (3) since it easily transforms to (1) or (2). Finding the longest left-extension from each index with more ones than zeros can be done in O(n log n) time and O(n) additional space (for just the longest valid substring in O(n) time, see here: Finding the longest non-negative sub array). With that preprocessing, finding the longest combination of valid, non-overlapping substrings can be done with dynamic programming in somewhat optimized O(n^2) time and O(n) additional space.

We start by traversing the string, storing sums representing the partial sum up to and including s[i], counting zeros as -1. We insert each partial sum in a binary tree where each node also stores an array of indexes where the value occurs, and the leftmost index of a value less than the node's value. (A substring from s[a] to s[b] has more ones than zeros if the prefix sum up to b is greater than the prefix sum up to a.) If a value is already in the tree, we add the index to the node's index array.

Since we are traversing from left to right, only when a new lowest value is inserted into the tree is the leftmost-index-of-lower-value updated — and it's updated only for the node with the previous lowest value. This is because any nodes with a lower value would not need updating; and if any nodes with lower values were already in the tree, any nodes with higher values would already have stored the index of the earliest one inserted.

The longest valid substring to the left of each index extends to the leftmost index with a lower prefix sum, which can be easily looked up in the tree.

To get the longest combination, let f(i) represent the longest combination up to index i. Then f(i) equals the maximum of the length of each valid left extension possible to index j added to f(j-1).

Upvotes: 2

Malcolm McLean
Malcolm McLean

Reputation: 6404

Dynamic programming.

We have a string. If it is positive, that's our answer. Otherwise we need to trim each end until it goes positive, and find each pattern of trims. So for each length (N-1, N-2, N-3) etc, we've got N- length possible paths (trim from a, trim from b) each of which give us a state. When state goes positive, we've found out substring.

So two lists of integers, representing what happens if we trim entirely from a or entirely from b. Then backtrack. If we trim 1 from a, we must trim all the rest from b, if we trim two from a, we must trim one fewer from b. Is there an answer that allows us to go positive?

We can quickly eliminate because the answer must be at a maximum, either max trimming from a or max trimming from b. If the other trim allows us go positive, that's the result.

pseudocode:

N = length(string);
Nones = countones(string);
Nzeros = N - Nones;
if(Nones > Nzeroes)
   return string

vector<int> cuta;
vector<int> cutb;
int besta = Nones - Nzeros;
int bestb = Nones - Nzeros;

cuta.push_back(besta);
cutb.push_back(bestb);
bestia = 0;
bestib = 0;

for(i=0;i<N;i++)
{
   cuta.push_back( string[i] == 1 ? cuta.back() - 1 : cuta.back() +1);
   cutb.push_back( string[N-i-1] == 1 ? cutb.back() -1 : cutb.back()+1);

   if(cuta.back() > besta)
   {
      besta = cuta.back();
      bestia = i;
   }
  if(cutb.back() > bestb)
  {
    bestb = cutb.back();
    bestib = i;
  }

   // checks, is a cut from wholly from a or b going to send us positive
   if(besta == 1)
      answer = substring(string, bestia, N);
   if(bestb == 1)
      answer = substring(string, 0, N - bestib);

   // if not, is a combined cut from current position to the
   // the peak in the other distribution going to send us positive?
   if(Nones - Nzeros + besta + cutb.back() == 1)
  {
     answer = substring(string, bestai, N - i);
  }
  if(Nones - Nzeros + cuta.back() + bestb == 1)
  {
      answer = substring(string, i, N - bestbi);
  }

}
/*if we get here the string was all zeros and no positive substring */

This is untested and the final checks are a bit fiddly and I might have made an error somewhere, but the algorithm should work more or less as described.

Upvotes: 0

Related Questions