CODEWITHSUNDEEP
algorithmsequence
ousko
ousko

Reputation: 41

Longest contiguous subsequence without repeated numbers

I have the following task:

Find the length of the longest consecutive subsequence such that all numbers in it are unique.

Now if I do not assume that elements of my sequence are not from some fixed alphabet but they can be, for example, arbitrary numbers, is this task still solvable in linear time?

Upvotes: 0

Views: 757

Answers (1)

kevmo314
kevmo314

Reputation: 4317

This can be solved using two pointers and a set of elements. Let i be the head pointer and j be the tail pointer, both starting at zero.

For each index i, add the element S[i], where S is the sequence to the set if the element does not exist in the set. If it does exist, then increment j until S[i] == S[j-1], removing each element from the set. At the end of the loop, store the max size of the element set.

This is linear time because both pointers iterate through the sequence at most n times and contains(), remove(), and add() on a hash set are amortized constant time.

int longestUnique(int[] S) {
  HashSet<Integer> elements = new HashSet<Integer>();
  int longest = 0;
  for (int i = 0, j = 0; i < S.length; i++) {
    if (elements.contains(S[i])) {
      do {
        elements.remove(S[j]);
      } while (S[j++] != S[i]);
    }
    elements.add(S[i]);
    longest = Math.max(longest, i - j + 1);
  }
  return longest;
}

Upvotes: 2

Related Questions