Sliding Window on Strings
The sliding window technique is also powerful for string problems, especially when dealing with substrings of a fixed length or with constraints like "longest substring without repeating characters".
1. Longest Substring Without Repeating Characters
Use two pointers (left, right) and a set to track characters in the current window.
public static int lengthOfLongestSubstring(String s) {
Set set = new HashSet<>();
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
while (set.contains(s.charAt(right))) {
set.remove(s.charAt(left));
left++;
}
set.add(s.charAt(right));
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
2. Minimum Window Substring
Find the smallest substring containing all characters of a pattern. This is a classic hard problem solved with sliding window and character frequency counts.
3. Longest Repeating Character Replacement
Given a string and k replacements, find the longest substring that can be made of the same character. Use sliding window tracking the most frequent character in the window.
Two Minute Drill
- Sliding window on strings often uses a set or map to track characters.
- Expand right pointer, shrink left when condition violated.
- Common problems: longest substring without repeating chars, smallest window containing all chars.
- These problems are frequently asked in interviews.
Need more clarification?
Drop us an email at career@quipoinfotech.com