Sunday, 4 January 2026

Sliding Window Pattern – All Problems Explained (Java)

Sliding Window Pattern – All Problems with Step-by-Step Iteration (Java)

Sliding Window is a powerful technique to solve contiguous subarray and substring problems efficiently by avoiding repeated calculations.

Problem Statement

Given arrays and strings, solve multiple classic problems involving contiguous subarrays or substrings using fixed-size and variable-size sliding window techniques.

Examples:

Input: [2,1,5,1,3,2], k = 3
Output: Max Sum Subarray = 9

Input: "ADOBECODEBANC", "ABC"
Output: BANC

Approaches Used

  • Fixed Size Sliding Window
  • Variable Size Sliding Window

Java Code Implementation


import java.util.*;

public class SlidingWindowAllProblems {

    /* =====================================================
       1. Maximum Sum Subarray of Size K
       ===================================================== */
    static int maxSumSubarray(int[] arr, int k) {
        int sum = 0;
        for (int i = 0; i < k; i++) sum += arr[i];

        int max = sum;
        for (int i = k; i < arr.length; i++) {
            sum += arr[i] - arr[i - k];
            max = Math.max(max, sum);
        }
        return max;
    }

    /* =====================================================
       2. First Negative Number in Every Window
       ===================================================== */
    static void firstNegativeInWindow(int[] arr, int k) {
        Deque dq = new ArrayDeque<>();

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < 0) dq.addLast(i);

            if (!dq.isEmpty() && dq.peekFirst() <= i - k)
                dq.pollFirst();

            if (i >= k - 1)
                System.out.print(dq.isEmpty() ? "0 " : arr[dq.peekFirst()] + " ");
        }
        System.out.println();
    }

    /* =====================================================
       3. Count Distinct Elements in Every Window
       ===================================================== */
    static void countDistinct(int[] arr, int k) {
        Map map = new HashMap<>();

        for (int i = 0; i < k; i++)
            map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);

        System.out.print(map.size() + " ");

        for (int i = k; i < arr.length; i++) {
            int left = arr[i - k];
            map.put(left, map.get(left) - 1);
            if (map.get(left) == 0) map.remove(left);

            map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
            System.out.print(map.size() + " ");
        }
        System.out.println();
    }

    /* =====================================================
       4. Average of Subarrays of Size K
       ===================================================== */
    static void averageSubarrays(int[] arr, int k) {
        int sum = 0;
        for (int i = 0; i < k; i++) sum += arr[i];

        System.out.print((double) sum / k + " ");

        for (int i = k; i < arr.length; i++) {
            sum += arr[i] - arr[i - k];
            System.out.print((double) sum / k + " ");
        }
        System.out.println();
    }

    /* =====================================================
       5. Maximum of All Subarrays of Size K
       ===================================================== */
    static void maxOfSubarrays(int[] arr, int k) {
        Deque dq = new ArrayDeque<>();

        for (int i = 0; i < arr.length; i++) {

            while (!dq.isEmpty() && arr[dq.peekLast()] <= arr[i])
                dq.pollLast();

            dq.addLast(i);

            if (dq.peekFirst() <= i - k)
                dq.pollFirst();

            if (i >= k - 1)
                System.out.print(arr[dq.peekFirst()] + " ");
        }
        System.out.println();
    }

    /* =====================================================
       6. Longest Substring Without Repeating Characters
       ===================================================== */
    static int longestUniqueSubstring(String s) {
        boolean[] freq = new boolean[256];
        int start = 0, max = 0;

        for (int end = 0; end < s.length(); end++) {
            while (freq[s.charAt(end)]) {
                freq[s.charAt(start)] = false;
                start++;
            }
            freq[s.charAt(end)] = true;
            max = Math.max(max, end - start + 1);
        }
        return max;
    }

    /* =====================================================
       7. Longest Substring with K Distinct Characters
       ===================================================== */
    static int longestKDistinct(String s, int k) {
        Map map = new HashMap<>();
        int start = 0, max = 0;

        for (int end = 0; end < s.length(); end++) {
            map.put(s.charAt(end), map.getOrDefault(s.charAt(end), 0) + 1);

            while (map.size() > k) {
                char left = s.charAt(start++);
                map.put(left, map.get(left) - 1);
                if (map.get(left) == 0) map.remove(left);
            }
            max = Math.max(max, end - start + 1);
        }
        return max;
    }

    /* =====================================================
       8. Smallest Subarray with Sum >= K
       ===================================================== */
    static int smallestSubarray(int[] arr, int k) {
        int start = 0, sum = 0, minLen = Integer.MAX_VALUE;

        for (int end = 0; end < arr.length; end++) {
            sum += arr[end];
            while (sum >= k) {
                minLen = Math.min(minLen, end - start + 1);
                sum -= arr[start++];
            }
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }

    /* =====================================================
       9. Minimum Window Substring
       ===================================================== */
    static String minWindow(String s, String t) {
        Map map = new HashMap<>();
        for (char c : t.toCharArray())
            map.put(c, map.getOrDefault(c, 0) + 1);

        int start = 0, count = map.size();
        int minLen = Integer.MAX_VALUE, minStart = 0;

        for (int end = 0; end < s.length(); end++) {
            char c = s.charAt(end);
            if (map.containsKey(c)) {
                map.put(c, map.get(c) - 1);
                if (map.get(c) == 0) count--;
            }

            while (count == 0) {
                if (end - start + 1 < minLen) {
                    minLen = end - start + 1;
                    minStart = start;
                }
                char left = s.charAt(start++);
                if (map.containsKey(left)) {
                    map.put(left, map.get(left) + 1);
                    if (map.get(left) > 0) count++;
                }
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLen);
    }

    /* =====================================================
       MAIN METHOD – MULTIPLE INPUTS
       ===================================================== */
    public static void main(String[] args) {

        System.out.println("Max Sum Subarray: " +
                maxSumSubarray(new int[]{2,1,5,1,3,2}, 3));

        System.out.print("First Negative: ");
        firstNegativeInWindow(new int[]{12,-1,-7,8,-15,30,16,28}, 3);

        System.out.print("Distinct Count: ");
        countDistinct(new int[]{1,2,1,3,4,2,3}, 4);

        System.out.print("Averages: ");
        averageSubarrays(new int[]{1,3,2,6,-1,4,1,8,2}, 5);

        System.out.print("Max of Subarrays: ");
        maxOfSubarrays(new int[]{1,3,-1,-3,5,3,6,7}, 3);

        System.out.println("Longest Unique Substring: " +
                longestUniqueSubstring("abcabcbb"));

        System.out.println("Longest K Distinct: " +
                longestKDistinct("aabacbebebe", 3));

        System.out.println("Smallest Subarray >= 7: " +
                smallestSubarray(new int[]{2,3,1,2,4,3}, 7));

        System.out.println("Minimum Window Substring: " +
                minWindow("ADOBECODEBANC", "ABC"));
    }
}

Explanation

1. Maximum Sum Subarray of Size K

Input: [2,1,5,1,3,2], k = 3

  • Initial window: [2,1,5] → sum = 8
  • Slide window → add 1, remove 2 → [1,5,1] → sum = 7
  • Slide window → add 3, remove 1 → [5,1,3] → sum = 9
  • Slide window → add 2, remove 5 → [1,3,2] → sum = 6

Output: 9

2. First Negative Number in Every Window

Input: [12,-1,-7,8,-15,30,16,28], k = 3

  • Window [12,-1,-7] → first negative = -1
  • Window [-1,-7,8] → first negative = -1
  • Window [-7,8,-15] → first negative = -7
  • Window [8,-15,30] → first negative = -15
  • Window [-15,30,16] → first negative = -15
  • Window [30,16,28] → no negative → 0

Output: -1 -1 -7 -15 -15 0

3. Count Distinct Elements in Every Window

Input: [1,2,1,3,4,2,3], k = 4

  • [1,2,1,3] → distinct = 3
  • [2,1,3,4] → distinct = 4
  • [1,3,4,2] → distinct = 4
  • [3,4,2,3] → distinct = 3

Output: 3 4 4 3

4. Average of Subarrays of Size K

Input: [1,3,2,6,-1,4,1,8,2], k = 5

  • [1,3,2,6,-1] → avg = 2.2
  • [3,2,6,-1,4] → avg = 2.8
  • [2,6,-1,4,1] → avg = 2.4
  • [6,-1,4,1,8] → avg = 3.6
  • [-1,4,1,8,2] → avg = 2.8

Output: 2.2 2.8 2.4 3.6 2.8

5. Maximum of All Subarrays of Size K

Input: [1,3,-1,-3,5,3,6,7], k = 3

  • [1,3,-1] → max = 3
  • [3,-1,-3] → max = 3
  • [-1,-3,5] → max = 5
  • [-3,5,3] → max = 5
  • [5,3,6] → max = 6
  • [3,6,7] → max = 7

Output: 3 3 5 5 6 7

6. Longest Substring Without Repeating Characters

Input: "abcabcbb"

  • "abc" → length 3
  • Repeat 'a' → shrink window
  • Continue maintaining unique window

Output: 3

7. Longest Substring with K Distinct Characters

Input: "aabacbebebe", k = 3

  • Expand window until > k distinct characters
  • Shrink window from left until condition is valid
  • Track max length during valid windows

Output: 7

8. Smallest Subarray with Sum ≥ K

Input: [2,3,1,2,4,3], k = 7

  • [2,3,1,2] → sum = 8 → shrink
  • [4,3] → sum = 7 → length = 2

Output: 2

9. Minimum Window Substring

Input: s = "ADOBECODEBANC", t = "ABC"

  • Expand window until all chars A, B, C included
  • Shrink window to minimize length
  • Smallest valid window = "BANC"

Output: BANC

Technique Used: Sliding Window (Fixed & Variable)

Sample Output

Max Sum Subarray: 9
First Negative: -1 -1 -7 -15 -15 0
Distinct Count: 3 4 4 3
Averages: 2.2 2.8 2.4 3.6 2.8
Max of Subarrays: 3 3 5 5 6 7
Longest Unique Substring: 3
Longest K Distinct: 7
Smallest Subarray >= 7: 2
Minimum Window Substring: BANC

Time & Space Complexity

Type Time Space
Sliding Window O(n) O(k)

Interview Tip

If the problem asks for a contiguous subarray or substring with constraints, Sliding Window should be your first optimization choice.

Practice More

  • Maximum vowels in a substring of size k
  • Longest subarray with at most k odd numbers

Category: Arrays, Strings
Difficulty: Easy → Medium
Techniques: Sliding Window, HashMap, Deque

Posted by at No comments:

Saturday, 3 January 2026

Naive Distinct Pattern Matching in Strings in Java

Naive Distinct Pattern Matching in Strings

An optimized version of naive pattern matching that skips unnecessary comparisons when the pattern contains all distinct characters.

Problem Statement

Given a text string txt and a pattern string pat (with all distinct characters), find and print all starting indices where the pattern occurs in the text.

Examples:

Input:
txt = "ABCABCD"
pat = "ABCD"

Output:
3

Input:
txt = "ABCEABCFABCD"
pat = "ABCD"

Output:
8

Approaches Used

  • Naive Pattern Matching
  • Naive Distinct Pattern Matching (Optimized)

Java Code Implementation


public class NaiveDistinctPatternMatching {

    public static void main(String[] args) {

        // Multiple test cases
        searchDistinctPattern("ABCABCD", "ABCD");        // Expected: 3
        searchDistinctPattern("ABCEABCFABCD", "ABCD");  // Expected: 8
        searchDistinctPattern("XYZABCDXYZ", "ABCD");    // Expected: 3
    }

    private static void searchDistinctPattern(String text, String pattern) {

        int n = text.length();
        int m = pattern.length();

        System.out.println("Text: " + text + ", Pattern: " + pattern);

        for (int i = 0; i <= n - m; ) {
            int j;

            // Match characters
            for (j = 0; j < m; j++) {
                if (text.charAt(i + j) != pattern.charAt(j)) {
                    break;
                }
            }

            // Full pattern matched
            if (j == m) {
                System.out.print(i + " ");
            }

            // Skip logic (key optimization)
            if (j == 0) {
                i++;
            } else {
                i = i + j;
            }
        }
        System.out.println("\n");
    }
}

Explanation

Approach 1: Naive Pattern Matching

  • Slide the pattern one character at a time.
  • Compare every character even if a mismatch occurs early.
  • Always increment index by 1.

Technique Used: Brute Force String Matching

Approach 2: Naive Distinct Pattern Matching

  • Works only when pattern characters are all distinct.
  • If a mismatch happens at index j, skip ahead by j characters.
  • Avoids rechecking characters that are guaranteed not to match.
  • Significantly reduces unnecessary comparisons.

Technique Used: Optimized Brute Force (Distinct Characters Optimization)

Sample Output

Text: ABCABCD, Pattern: ABCD
3

Text: ABCEABCFABCD, Pattern: ABCD
8

Text: XYZABCDXYZ, Pattern: ABCD
3

Time & Space Complexity

Approach Time Space
Naive Pattern Matching O((n - m + 1) × m) O(1)
Naive Distinct Pattern Matching O(n) O(1)

Interview Tip

Mention that this optimization works only when all characters in the pattern are distinct. Otherwise, use KMP for guaranteed linear performance.

Practice More

  • Compare Naive Distinct vs KMP with examples
  • Implement pattern matching using Z-algorithm

Category: Strings
Difficulty: Easy
Techniques: Brute Force, Pattern Matching, Optimization

Posted by at No comments:
Subscribe to: Comments (Atom)