Sliding Window
Java solutions with explanations, time and space complexity for Sliding Window problems from Blind 75.
Sliding Window
This section covers problems that can be efficiently solved using the sliding window technique. This pattern is particularly useful for array and string problems where you need to find subarrays or substrings that satisfy certain conditions.
1. Best Time to Buy and Sell Stock (Easy)
Problem: You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Example:
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.Solution:
class Solution {
public int maxProfit(int[] prices) {
if (prices.length < 2) return 0;
int minPrice = prices[0];
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
// Update minimum price seen so far
minPrice = Math.min(minPrice, prices[i]);
// Calculate potential profit if we sell at current price
int currentProfit = prices[i] - minPrice;
maxProfit = Math.max(maxProfit, currentProfit);
}
return maxProfit;
}
}Time Complexity: O(n) Space Complexity: O(1)
Key Insight: Keep track of the minimum price seen so far and calculate potential profit at each step.
2. Longest Substring Without Repeating Characters (Medium)
Problem: Given a string s, find the length of the longest substring without repeating characters.
Example:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.Solution:
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();
int left = 0, maxLength = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
// If character is already in set, move left pointer
while (set.contains(c)) {
set.remove(s.charAt(left));
left++;
}
set.add(c);
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
}Time Complexity: O(n) Space Complexity: O(min(m, n)) where m is the size of the character set
Alternative Approach (Using HashMap):
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> map = new HashMap<>();
int left = 0, maxLength = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (map.containsKey(c)) {
left = Math.max(left, map.get(c) + 1);
}
map.put(c, right);
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
}Time Complexity: O(n) Space Complexity: O(min(m, n))
3. Longest Repeating Character Replacement (Medium)
Problem: You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.
Return the length of the longest substring containing the same letter you can get after performing the above operations.
Example:
Input: s = "ABAB", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "ABBB".
The substring "BBBB" has the longest repeating letters, which is 4.Solution:
class Solution {
public int characterReplacement(String s, int k) {
int[] count = new int[26];
int left = 0, maxCount = 0, maxLength = 0;
for (int right = 0; right < s.length(); right++) {
count[s.charAt(right) - 'A']++;
maxCount = Math.max(maxCount, count[s.charAt(right) - 'A']);
// If window size - maxCount > k, we need to shrink the window
if (right - left + 1 - maxCount > k) {
count[s.charAt(left) - 'A']--;
left++;
}
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
}Time Complexity: O(n) Space Complexity: O(1) - fixed size array
Key Insight: The key insight is that we only need to track the maximum frequency of any character in the current window.
4. Permutation in String (Medium)
Problem: Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.
In other words, return true if one of s1’s permutations is the substring of s2.
Example:
Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").Solution:
class Solution {
public boolean checkInclusion(String s1, String s2) {
if (s1.length() > s2.length()) return false;
int[] s1Count = new int[26];
int[] s2Count = new int[26];
// Initialize the count for s1
for (char c : s1.toCharArray()) {
s1Count[c - 'a']++;
}
// Initialize the sliding window
for (int i = 0; i < s1.length(); i++) {
s2Count[s2.charAt(i) - 'a']++;
}
// Check if the first window is a permutation
if (matches(s1Count, s2Count)) return true;
// Slide the window
for (int i = s1.length(); i < s2.length(); i++) {
s2Count[s2.charAt(i) - 'a']++;
s2Count[s2.charAt(i - s1.length()) - 'a']--;
if (matches(s1Count, s2Count)) return true;
}
return false;
}
private boolean matches(int[] s1Count, int[] s2Count) {
for (int i = 0; i < 26; i++) {
if (s1Count[i] != s2Count[i]) return false;
}
return true;
}
}Time Complexity: O(n) Space Complexity: O(1) - fixed size arrays
5. Minimum Window Substring (Hard)
Problem: 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.
Example:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.Solution:
class Solution {
public String minWindow(String s, String t) {
if (s.length() < t.length()) return "";
Map<Character, Integer> tCount = new HashMap<>();
Map<Character, Integer> windowCount = new HashMap<>();
// Count characters in t
for (char c : t.toCharArray()) {
tCount.put(c, tCount.getOrDefault(c, 0) + 1);
}
int left = 0, minLeft = 0, minLen = Integer.MAX_VALUE;
int required = tCount.size();
int formed = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
windowCount.put(c, windowCount.getOrDefault(c, 0) + 1);
if (tCount.containsKey(c) && windowCount.get(c).intValue() == tCount.get(c).intValue()) {
formed++;
}
// Try to minimize the window
while (left <= right && formed == required) {
c = s.charAt(left);
if (right - left + 1 < minLen) {
minLen = right - left + 1;
minLeft = left;
}
windowCount.put(c, windowCount.get(c) - 1);
if (tCount.containsKey(c) && windowCount.get(c).intValue() < tCount.get(c).intValue()) {
formed--;
}
left++;
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(minLeft, minLeft + minLen);
}
}Time Complexity: O(n) Space Complexity: O(k) where k is the number of unique characters in t
6. Sliding Window Maximum (Hard)
Problem: 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:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]Solution:
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length == 0 || k == 0) return new int[0];
Deque<Integer> deque = new LinkedList<>();
int[] result = new int[nums.length - k + 1];
for (int i = 0; i < nums.length; i++) {
// Remove elements outside the window
while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
deque.pollFirst();
}
// Remove smaller elements from the back
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
deque.offerLast(i);
// Add maximum to result
if (i >= k - 1) {
result[i - k + 1] = nums[deque.peekFirst()];
}
}
return result;
}
}Time Complexity: O(n) Space Complexity: O(k)
Key Insight: Use a monotonic deque to maintain the maximum element in the current window.
7. Longest Substring with At Most K Distinct Characters (Medium)
Problem: Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.
Example:
Input: s = "eceba", k = 2
Output: 3
Explanation: The substring is "ece" with length 3.Solution:
class Solution {
public int lengthOfLongestSubstringKDistinct(String s, int k) {
if (k == 0) return 0;
Map<Character, Integer> count = new HashMap<>();
int left = 0, maxLength = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
count.put(c, count.getOrDefault(c, 0) + 1);
// Shrink window if we have more than k distinct characters
while (count.size() > k) {
char leftChar = s.charAt(left);
count.put(leftChar, count.get(leftChar) - 1);
if (count.get(leftChar) == 0) {
count.remove(leftChar);
}
left++;
}
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
}Time Complexity: O(n) Space Complexity: O(k)
8. Substring with Concatenation of All Words (Hard)
Problem: You are given a string s and an array of strings words. All the strings of words are of the same length.
A concatenated substring in s is a substring that contains all the strings of any permutation of words concatenated.
For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated substring because it is not the concatenation of any permutation of words.
Return the starting indices of all the concatenated substrings in s. You can return the answer in any order.
Example:
Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]Solution:
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> result = new ArrayList<>();
if (s.length() == 0 || words.length == 0) return result;
int wordLength = words[0].length();
int totalLength = wordLength * words.length;
Map<String, Integer> wordCount = new HashMap<>();
for (String word : words) {
wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
}
for (int i = 0; i <= s.length() - totalLength; i++) {
Map<String, Integer> seen = new HashMap<>();
boolean valid = true;
for (int j = 0; j < words.length; j++) {
String word = s.substring(i + j * wordLength, i + (j + 1) * wordLength);
if (!wordCount.containsKey(word)) {
valid = false;
break;
}
seen.put(word, seen.getOrDefault(word, 0) + 1);
if (seen.get(word) > wordCount.get(word)) {
valid = false;
break;
}
}
if (valid) {
result.add(i);
}
}
return result;
}
}Time Complexity: O(n * m * k) where n is the length of s, m is the number of words, and k is the length of each word Space Complexity: O(m)
Key Takeaways
- Window Size: Sliding window problems often involve maintaining a window of variable or fixed size
- Hash Maps: Use hash maps to track character frequencies or counts
- Two Pointers: Use left and right pointers to maintain the window boundaries
- Optimization: Look for ways to avoid unnecessary computations within the window
- Edge Cases: Consider empty strings, single characters, and boundary conditions
- Character Sets: Be mindful of the character set size for space complexity analysis