Sliding Window on String

Longest Unique Substring

Expand the window right. If a duplicate character enters, shrink from the left until the duplicate is removed. Track the maximum window length seen. Uses a set or map to track window contents.

O(n)

O(min(n, m))

How It Works

Finding the longest substring without repeating characters is a classic variable-size sliding window. Maintain two pointers bounding the current window and a set (or map of last-seen indices) describing its contents. Advance the right pointer one character at a time; if the new character already exists in the window, advance the left pointer until the duplicate is evicted, then record the window length.

Each pointer only moves forward, so every character is added and removed at most once, giving O(n) time — a huge win over the O(n²) or worse cost of testing every substring. Storing last-seen indices lets the left pointer jump directly past a duplicate instead of walking one step at a time.

Step-by-Step Visualization

Find longest substring without repeating chars

Window [0..2]

Windowabc

Max3

1/4

Code

Java

static int lengthOfLongestSubstring(String s) {
  Map<Character, Integer> map = new HashMap<>();
  int left = 0, maxLen = 0;

  for (int right = 0; right < s.length(); right++) {
    if (map.containsKey(s.charAt(right))) {
      left = Math.max(left, map.get(s.charAt(right)) + 1);
    }
    map.put(s.charAt(right), right);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}

Tips & Gotchas

1Use a hash map to track the last seen index of each character

2Update left pointer to max(left, lastSeen[char] + 1)

3Window always contains unique characters only

Practice Problems

1Longest Substring Without Repeating Characters
2Longest Substring with At Most K Distinct Characters
3Longest Repeating Character Replacement
4Fruit Into Baskets

About the Sliding Window on String Pattern

Apply the sliding window technique to strings. Use a frequency map inside the window to track character counts. Expand or shrink the window based on whether the current set of characters satisfies the problem's condition.

Key insight

Think of strings as arrays of characters. Frequency maps solve most comparison problems. For substring search, know KMP or rolling hash to beat O(n·m).

Common String Interview Problems

Longest Substring Without Repeating Characters
Valid Anagram
Longest Palindromic Substring
Minimum Window Substring
Group Anagrams

Frequently Asked Questions

Why is the sliding window O(n) when there are two nested-looking loops?

Amortized analysis: the left and right pointers each traverse the string at most once, so the total work across all iterations is bounded by 2n. The inner while loop cannot run more times overall than the number of characters the left pointer can move.

When should the window shrink versus reset entirely?

Shrink incrementally when partial window contents remain valid, which is the common case for uniqueness constraints. If you store last-seen indices in a map, you can jump the left pointer straight to one past the previous occurrence, skipping the character-by-character shrink.