In the world of algorithms and data structures, there are many efficient methods that allow solving various problems with minimal computational resources. One such powerful tool is the Sliding Window Pattern, or the "sliding window" technique. This method allows you to confidently control the processing of data in sequences using a fixed-length dynamic window approach. The main idea of a sliding window is that instead of directly iterating or processing all data elements, we narrow the focus to a certain subset of elements that can be changed and updated as we move along the sequence. This technique finds application in various problems, from finding the maximum substring to time series analysis.
In this article, we will introduce you to the concept of the Sliding Window Pattern by providing a brief description of the theory behind it. We will look at how this method works in the context of data processing, illustrating its application with practical examples. In addition, we will share useful tips on choosing the right situations for using a sliding window and optimizing your code.
So, the first thing you want to do is identify a problem that utilizes the sliding window paradigm.
Given a string s
, find the length of the longest substring without repeating characters.
Constraints:
0 <= s.length <= 5 * 10^4
s
consists of English letters, digits, symbols, and spaces.
Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
The idea is simple, we fix one letter and iterate over the rest of the string until we encounter a duplicate. We save all the letters in the set, and as soon as we find a duplicate letter, we shift the left border by 1 and start over.
This is a simple but inefficient approach.
Complexity:
O(n*n)
O(n)
public int lengthOfLongestSubstring(String s) {
int max = 0;
for (int left=0; left<s.length(); stleftart++) {
Set<Character> set = new HashSet<>();
for (int right=left; right<s.length(); right++) {
if (left != right && set.contains(s.charAt(right))) {
break;
}
set.add(s.charAt(right));
}
max = Math.max(max, set.size());
}
return max;
}
The idea of optimization is that we don't want to do only 1 step as soon as we meet a duplicate and start all over again. We will move the left border as long as there is a duplicate.
Complexity:
Time complexity: O(n)
Space complexity: O(n)
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();
int max = 0;
for (int i=0; i<s.length(); i++) {
char c = s.charAt(i);
if (set.contains(c)) {
while (c != s.charAt(i - set.size())) {
set.remove(s.charAt(i - set.size()));
}
} else {
set.add(c);
}
if (set.size() > max) max = set.size();
}
return max;
}
I want to note that I do not store the left border in a separate variable (although it is possible).
Since the left border is only needed when we encounter a duplicate, so I know exactly how many unique characters there were: set.size()
.
Therefore, I can find the left border by the formula: i - set.size()
.
The algorithm listed above gives us the following result.
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.
Constraints:
1 <= s.length <= 105
s
consists of only uppercase English letters.0 <= k <= s.length
Example 1:
Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.
Example 2:
Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.
There may exists other ways to achive this answer too.
This is a standard problem for applying the sliding window
technique, we must keep the "window" within certain constraints, in this case the constraint will be the presence of k
characters different from the most common.
The idea is to move end
and check that the area between start
and end
can be represented by a single character and we will make less than k
replacements. If more than k
replacements need to be made between start
and end
, then we will move start
until the rule is satisfied again.
public int characterReplacement(String s, int k) {
// Frequency map to store character frequencies within window
Map<Character, Integer> charFreqMap = new HashMap<>();
int start = 0; // Sliding window start
int maxFreq = 0; // Store frequency of most frequent character within window
int maxLength = 0; // Store maximum length of substring with same letters
for (int end = 0; end < s.length(); end++) {
char endChar = s.charAt(end);
charFreqMap.put(endChar, charFreqMap.getOrDefault(endChar, 0) + 1);
// Update maxFreq with current character's frequency
maxFreq = Math.max(maxFreq, charFreqMap.get(endChar));
// Calculate the number of characters that need to be replaced
int replacementsNeeded = (end - start + 1) - maxFreq;
// Check if replacements needed exceed k
while (replacementsNeeded > k) {
char leftChar = s.charAt(start);
charFreqMap.put(leftChar, charFreqMap.get(leftChar) - 1);
start++; // Move start to shrink window
}
// Update maxLen with current window size
maxLength = Math.max(maxLength, end - start + 1);
}
return maxLength;
}
I hope this article helped you understand how to solve this type of problem. I will be glad for your feedback.
See you soon! ✌