Maximal unique continuous subsequence

Question

Given a sequence of integer numbers:

a[0], a[1], a[2], ..., a[n]

Subsequencea[i]...a[j] is unique if the following is true:

for each x, y between i and j and x != y:
    a[x] != a[y]

I need to find length of maximal unique, continuous subsequence

My approaches:

I tried many heuristic approaches, but they didn't work.

Then I wrote bruteforce, it gave O(n^3) complexity, which is impossible to calc if n = 10^6

ans = 1
for i in [0, n]
    for j in [i, n]
        if unique a[i]...a[j]
            ans = max(ans, j-i+1)

I think it is typical dp problem, but don't know how to proceed

Answer 1

Create hashmap (or use boolean array if range of values is rather short).

Make two indexes - left and right, set them in the beginning.

Move right index. At every step check if t = A[right] already is in map. Stop when true.

Move left index, removing A[left] from map until value equal to t is met.

Repeat move steps until sequence end

The largest difference between right and left is needed maximal length

Answer 2

First of all, we could somewhat limit the operations using the following observation: if we found some unique sequence, then we don't have to check any sequence which is shorter. So we iterate j in [i+ans, n].

Next, if we know that uniqueness breaks for sequence from i to j, we don't have to expand it any further - we know that no longer sequence with i as start would be unique. So on the else statement of your check we just break the inner loop.

This way the iterations count seems to be something like O(n), since the j index will never go back.

---

upd: About the Ishpreet's answer (since I can't comment yet, I'll post it here).
This code won't work properly for sequences where the longest subsequence is not the first one. For example, consider this array: [2,3,4,3,1,5,2]. The correct answer would be 5 - the length of 4,3,1,5,2; but the answer given by the code above will be 3. The reason is that this code essentially drops all the sequence collected before the first duplicate came, which is not what we need, since we could take the part after the first duplicating number, including the second (which is not duplicating now) - like in this example.

Furthermore, this approach suffers from one fundamental problem. If we don't store (or otherwise check) the duplicate position, we can't know if it ever interfere with currently found subsequence, and so we don't know how much exactly we must drop (and do we need at all). It might be way before current subsequence started, shadowed by another duplicate; or it may be just here, in the previous number, forcing us to start anything from scratch.

Here's a piece of code trying to cover these cases (but it is yet to check its full correctness):

var map = {}
var arr = [2,3,4,4,5,1,6,2,8,5,9,3];
var ans = 1, currentSeqLength = 0;

for(var i=0; i<arr.length; i++){
  if(arr[i] in map && map[arr[i]] >= i - currentSeqLength) {
    currentSeqLength -= map[arr[i]];
  } else {
    currentSeqLength++;
  }
  map[arr[i]] = i;
  ans = Math.max(ans, currentSeqLength);
}

console.log(ans); // 6 i.e. Length of 4,5,1,6,2,8

Answer 3

This can be done in O(n).

You can use a hashmap or an Object in case of Javascript. Then keep a variable to track the maximum length of subsequence so far.

On each iteration just check if that value is present in hash map or not.

var map = {}
var arr = [2,3,4,5,1,3,2];
var ans = 1, currentSeqLength = 0;

for(var i=0; i<arr.length; i++){
  if(arr[i] in map) currentSeqLength = 0;
  else map[arr[i]] = true;
  currentSeqLength++;
  ans = Math.max(ans, currentSeqLength);
}

console.log(ans); // 5 i.e. Length of 2,3,4,5,1