Longest Unique Segment — Problem Statement & Solution Guide
Problem Description
Given an array of integers packetTypes, find the length of the longest continuous segment with no repeating elements.
Examples
Input
[1, 2, 3, 1, 2, 3, 4]
Output
4
Explanation: Step-by-step: with input [1, 2, 3, 1, 2, 3, 4], we find the longest continuous segment with no repeating elements. The longest segment is [1, 2, 3, 4] which has a length of 4.
Input
[1, 1, 1, 1, 1]
Output
1
Explanation: Step-by-step: with input [1, 1, 1, 1, 1], we find the longest continuous segment with no repeating elements. The longest segment is [1] which has a length of 1.
Constraints
- 0 <= s.length <= 5 * 10^4
- s consists of English letters, digits, symbols and spaces.
Optimal Approach & Strategy
Sliding window with left and right pointers. Add s[right] to set. If it exists in set, remove s[left] from set and increment left until the duplicate is gone. Update maxLength. Time O(N), Space O(min(N, charset)).
Brute Force Approach
Check all substrings for uniqueness. Time O(N^3).
Verified Code Solutions
function solution(packetTypes) {
let maxLength = 0;
let left = 0;
let uniqueElements = new Set();
for (let right = 0; right < packetTypes.length; right++) {
while (uniqueElements.has(packetTypes[right])) {
uniqueElements.delete(packetTypes[left]);
left++;
}
uniqueElements.add(packetTypes[right]);
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}class Solution {
public:
int solution(vector<int>& packetTypes) {
int maxLength = 0;
int left = 0;
unordered_set<int> uniqueElements;
for (int right = 0; right < packetTypes.size(); right++) {
while (uniqueElements.find(packetTypes[right]) != uniqueElements.end()) {
uniqueElements.erase(packetTypes[left]);
left++;
}
uniqueElements.insert(packetTypes[right]);
maxLength = max(maxLength, right - left + 1);
}
return maxLength;
}
};class Solution {
public int solution(int[] packetTypes) {
int maxLength = 0;
int left = 0;
Set<Integer> uniqueElements = new HashSet<>();
for (int right = 0; right < packetTypes.length; right++) {
while (uniqueElements.contains(packetTypes[right])) {
uniqueElements.remove(packetTypes[left]);
left++;
}
uniqueElements.add(packetTypes[right]);
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
}def solution(packetTypes):
max_length = 0
left = 0
unique_elements = set()
for right in range(len(packetTypes)):
while packetTypes[right] in unique_elements:
unique_elements.remove(packetTypes[left])
left += 1
unique_elements.add(packetTypes[right])
max_length = max(max_length, right - left + 1)
return max_lengthfunction solution(packetTypes) {
let maxLength = 0;
let left = 0;
let uniqueElements = new Set();
for (let right = 0; right < packetTypes.length; right++) {
while (uniqueElements.has(packetTypes[right])) {
uniqueElements.delete(packetTypes[left]);
left++;
}
uniqueElements.add(packetTypes[right]);
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}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.