Longest Substring Without Repeating Characters
Given a string s, find the length of the longest substring without duplicate characters.
Input: s = “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3. Note that “bca” and “cab” are also correct answers.
Use set to keep track of characters in sliding window, drop characters until next character to add (at current endWindow index) is not part of the set
Track max length at each iteration and return that
if (s==null || s.length()==0) return 0;
Set<Character> charInWindow = new HashSet<>();
int startIndex=0;
int result=0;
for(int endIndex=0; endIndex < s.length(); endIndex++) {
char toAdd = s.charAt(endIndex);
while(charInWindow.contains(toAdd)) {
charInWindow.remove(s.charAt(startIndex));
startIndex++;
}
charInWindow.add(toAdd);
result = Math.max(result, endIndex - startIndex + 1);
}
return result;Sliding Window Maximum
You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.
Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max
————— —–
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
Use a monotic queue to store only numbers that are in decreasing order
int[] result = new int[nums.length - k + 1];
Deque<Integer> queue = new LinkedList<>();
int resultIndex = 0;
int windowStart=0;
for(int windowEnd = 0; windowEnd < nums.length; windowEnd++) {
int currentNumber = nums[windowEnd];
while(!queue.isEmpty() && queue.peekLast()<currentNumber)
queue.pollLast();
queue.addLast(currentNumber);
if (windowEnd >= k-1) {
result[resultIndex++] = queue.peekFirst();
if (queue.peekFirst()==nums[windowStart])
queue.pollFirst();
windowStart++;
}
}
return result;Minimum Window Substring
Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string “”.
The testcases will be generated such that the answer is unique.
Input: s = “ADOBECODEBANC”, t = “ABC”
Output: “BANC”
Explanation: The minimum window substring “BANC” includes ‘A’, ‘B’, and ‘C’ from string t.
Brute force: check every possible substring -> O(N^3) time
Expand the window until we have all characters from t in it
Then try to make it smaller by moving the start inwards until we don’t lose any character in t
Take the minimum length of all such valid windows
if (s==null || t==null) return "";
int windowStart = 0, resultStart=0, resultLength=s.length()+1;
Map<Character, Integer> map = new HashMap<>();
for(char c: t.toCharArray()) {
map.put(c, map.getOrDefault(c, 0)+1);
}
int numberOfCharactersMatched = 0;
for(int windowEnd = 0; windowEnd < s.length(); windowEnd++) {
char c = s.charAt(windowEnd);
if (map.containsKey(c)) {
if (map.get(c) > 0) numberOfCharactersMatched++;
map.put(c, map.get(c)-1);
}
if (numberOfCharactersMatched == t.length()) {//try to shrink the window
while(!map.containsKey(s.charAt(windowStart)) || map.get(s.charAt(windowStart)) < 0) {
if (map.getOrDefault(s.charAt(windowStart), 0) < 0) {
map.put(s.charAt(windowStart), map.get(s.charAt(windowStart))+1);
}
windowStart++;
}
if (resultLength > windowEnd - windowStart + 1) {
resultLength = windowEnd - windowStart + 1;
resultStart = windowStart;
}
}
}
return resultLength > s.length() ? "" : s.substring(resultStart, resultStart+resultLength);Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
Given an array of integers nums and an integer limit, return the size of the longest non-empty subarray such that the absolute difference between any two elements of this subarray is less than or equal to limit.
Input: nums = [10,1,2,4,7,2], limit = 5
Output: 4
Explanation: The subarray [2,4,7,2] is the longest since the maximum absolute diff is |2-7| = 5 <= 5.
- Use sliding window with two deques: decreasing and increasing
- For every element, maintain both deques in their - respective orders
- Find the absolute difference in the subarray by taking the abs of difference between first elements of both deques
- When this difference exceeds limit, start shrinking the window
- update max length every iteration to the max seen so far
Deque<Integer> increasing = new LinkedList<>(); Deque<Integer> decreasing = new LinkedList<>(); int windowStart=0, result = 0; for(int windowEnd=0; windowEnd < nums.length; windowEnd++) { int toAdd = nums[windowEnd]; while(!decreasing.isEmpty() && decreasing.peekLast() < toAdd) decreasing.pollLast(); decreasing.addLast(toAdd); while(!increasing.isEmpty() && increasing.peekLast() > toAdd) increasing.pollLast(); increasing.addLast(toAdd); while(Math.abs(decreasing.peekFirst() - increasing.peekFirst()) > limit) { int numberAtStart = nums[windowStart]; if (decreasing.peekFirst() == numberAtStart) decreasing.pollFirst(); if (increasing.peekFirst() == numberAtStart) increasing.pollFirst(); windowStart++; } result = Math.max(result, windowEnd - windowStart+1); } return result;
O(n) space and time complexity
