CODEWITHSUNDEEP
c++algorithm
Piotr Wasilewicz
Piotr Wasilewicz

Reputation: 1821

Find length of longest binary subsequence with at most k ones

as can be seen in title, I need to find length of longest binary subsequence with at most k ones. For instance:

k = 3, binary_seq = 11100001101011010000011, answer is: 10 (because longest subsequence is 11100001101011010000011)

k = 1, binary_seq = 00101001001, answer is: 5 (because longest subsequence is 00101001001)

I did it but in quadratic time (I guess)

#include <iostream>
#include <vector>

using namespace std;

template <typename V>
void pop_front(V & v)
{
    v.erase(v.begin());
}

int main() {
    int k,maxLength=0,lengthOfSequence;
    bool one;
    string bin_seq;
    lengthOfSequence = 1;
    vector<unsigned> myList;
    cin >> k;
    cin >> bin_seq;
    for(char num : bin_seq) {
        myList.push_back(0);
        if (num == '1') {
            for(int i = 0; i < lengthOfSequence;++i)
                ++myList[i];
        }
        for(int i = 0; i < lengthOfSequence;++i) {
            if(myList[i] <= k) {
                if (lengthOfSequence-i > maxLength) {
                    maxLength = lengthOfSequence-i;
                }
            }
        }
        lengthOfSequence++;
        while(myList[0]>k) {
            pop_front(myList);
            lengthOfSequence--;
        }

    }
    cout << maxLength << '\n';
    return 0;
}

how to do it in smaller time complexity?

Upvotes: 1

Views: 668

Answers (2)

Saurav Sahu
Saurav Sahu

Reputation: 13934

Lets say the input is 1101011010000011

1101011010000011
fedcba9876543210  << Bit Positions

Now create an array containing indexes were bit are set. Maintain i and j as j = (i + k-1) while advancing both together by 1.

For K = 3
Array: 0 1 7 9 a c e f
i,j:   ^   ^
       max = 9 - (0-1) - 1

      -----------------------

       0 1 7 9 a c e f
i++,j++: ^   ^      
      max = (arr[j+1] - arr[i-1]) - 1
          = a - 0 - 1 = 9

      -----------------------

      0 1 7 9 a c e f
          ^   ^     
      max = (arr[j+1] - arr[i-1]) - 1
          =   c - 1 - 1 = 12- 1- 1 = 10 (as 10 > 9)

      -----------------------

      0 1 7 9 a c e f
            ^   ^       
      max = (e - 7) - 1 = 14 - 7 - 1 = 6. So max = 10

      -----------------------

      0 1 7 9 a c e f
              ^   ^     
      max = f-9 - 1 = 15-9-1 = 5 (<10).

      -----------------------

          0 1 7 9 a c e f
                    ^   ^       
      max = (f+1) - a - 1 = 16-10-1 = 5 (<10).


      So, max = 10;

Upvotes: 1

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726599

You can do it in O(n) with this algorithm:

  • Make two indexes, one for the beginning and one for the end of the desired subsequence
  • Keep expanding the sequence by increasing the end index until you reach the position of k+1-st 1
  • Before you continue expanding the sequence past k+1-st 1, shrink the sequence by "pulling in" the start to skip over the earliest 1 in the sequence
  • Each time you expand the sequence by increasing end, record the max length of the sequence
  • Once you reach the end of the sequence, max will have the longest subsequence with at most k ones in it.

Upvotes: 4

Related Questions