Sliding Window Algorithm in Java
The sliding window algorithm is a common technique used to solve problems involving sequences
(like arrays or strings)
by creating a "window" that can expand and contract over the data structure. This approach is
particularly useful for
optimizing algorithms that would otherwise involve nested loops, allowing you to solve problems in
linear time.
How It Works:
1. Initialization: Start with two pointers (usually referred to as 'start' and 'end') that define the current
window
in the array or string.
2. Expansion: Move the 'end' pointer to expand the window and include more elements.
3. Contraction: When a condition is met (e.g., a specific sum is exceeded, or a duplicate is found),
move the 'start'
pointer to contract the window.
4. Calculation/Output: During the iteration, you can keep track of metrics and update results
accordingly.
Applications:
- Finding the maximum or minimum of all contiguous subarrays of size k.
- Finding the longest substring without repeating characters.
- Counting distinct elements in every window of size k.
- Solving problems related to subarray sums.
Example: Longest Substring Without Repeating Characters
Let's implement a sliding window algorithm in Java to find the length of the longest substring without
repeating characters.
Java Code Example:
import java.util.HashMap;
class Solution {
public int lengthOfLongestSubstring(String s) {
HashMap<Character, Integer> charIndexMap = new HashMap<>();
int maxLength = 0;
int start = 0; // Left pointer for the sliding window
for (int end = 0; end < s.length(); end++) {
char currentChar = s.charAt(end);
// If the character is already in the map, move the start pointer
if (charIndexMap.containsKey(currentChar)) {
start = Math.max(charIndexMap.get(currentChar) + 1, start);
// Update the last seen index of the current character
charIndexMap.put(currentChar, end);
// Calculate the max length
maxLength = Math.max(maxLength, end - start + 1);
return maxLength;
public static void main(String[] args) {
Solution solution = new Solution();
String input = "abcabcbb";
int result = solution.lengthOfLongestSubstring(input);
System.out.println("Length of longest substring without repeating characters: " + result);
