Longest Distinct Circular Subsequence ā Problem Statement & Solution Guide
Problem Description
Given a circular array of integers elements, determine the length of the longest contiguous subsequence that contains no duplicate elements.
Examples
Input
[1, 2, 3, 1, 2, 3]
Output
3
Explanation: Step-by-step: Given the input [1, 2, 3, 1, 2, 3], we first find the longest contiguous subsequence with no duplicates. The longest contiguous subsequence with no duplicates is [1, 2, 3]. The length of this subsequence is 3.
Input
[1]
Output
1
Explanation: Step-by-step: Given the input [1], we first find the longest contiguous subsequence with no duplicates. The longest contiguous subsequence with no duplicates is [1]. The length of this subsequence is 1.
Constraints
- The length of the input array is between 1 and 1000.
- Each element in the array is an integer between 1 and 10000.
Optimal Approach & Strategy
The optimized approach utilizes a sliding window technique in conjunction with a hash set to efficiently track unique elements within the current window, allowing for a significant reduction in time complexity.
Brute Force Approach
The brute-force approach involves checking every possible subsequence of the given array, which results in a time complexity of O(nĀ²), making it inefficient for large inputs.
Verified Code Solutions
function longestDistinctCircularSubsequence(elements) {
if (elements.length === 0) return 0;
let maxLen = 0;
let set = new Set();
let left = 0;
for (let right = 0; right < elements.length; right++) {
while (set.has(elements[right])) {
set.delete(elements[left]);
left++;
}
set.add(elements[right]);
maxLen = Math.max(maxLen, right - left + 1);
}
return Math.max(maxLen, 1);
}class Solution {
public int longestDistinctCircularSubsequence(int[] nums) {
int n = nums.length;
int maxLength = 0;
for (int i = 0; i < n; i++) {
Set<Integer> seen = new HashSet<>();
int currentLength = 0;
for (int j = 0; j < n; j++) {
if (!seen.contains(nums[j % n])) {
seen.add(nums[j % n]);
currentLength++;
maxLength = Math.max(maxLength, currentLength);
} else {
break;
}
}
}
return maxLength;
}
}def longest_distinct_circular_subsequence(nums):
n = len(nums)
max_length = 0
for i in range(n):
seen = set()
current_length = 0
for j in range(n):
if nums[j % n] not in seen:
seen.add(nums[j % n])
current_length += 1
max_length = max(max_length, current_length)
else:
break
return max_lengthfunction longestDistinctCircularSubsequence(elements) {
if (elements.length === 0) return 0;
let maxLen = 0;
let set = new Set();
let left = 0;
for (let right = 0; right < elements.length; right++) {
while (set.has(elements[right])) {
set.delete(elements[left]);
left++;
}
set.add(elements[right]);
maxLen = Math.max(maxLen, right - left + 1);
}
return Math.max(maxLen, 1);
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.