Definition
- Sliding window maintains a variable-size window of unique characters using two pointers (left and right).
- HashSet tracking stores characters currently inside the window, providing O(1) duplicate detection.
- Expand the right edge to include new characters one at a time.
- Contract the left edge when a duplicate appears, removing characters until the duplicate is gone.
- Maximum tracking updates the best window size after each valid state as
right - left + 1. - Linear time is guaranteed because each pointer traverses the string at most once.
The National Bank of India scans a stream of single-character transaction codes and wants the longest run with no repeated code, as a measure of operation diversity. Rajesh keeps a stretchy window over the codes. He pushes the right edge forward to grab new codes as long as they are all different. The instant a code repeats inside the window, he pulls the left edge forward past the earlier copy so the window is clean again, and remembers the widest window seen.
Understanding the Concepts
What is the problem?
Given a string, find the length of the longest contiguous substring that contains no repeated character. For "abcabcbb", the answer is 3 because "abc" is the longest substring with all unique characters. This is a classic sliding window problem that appears frequently in coding interviews.
package com.bank.dsa;
import java.util.HashSet;
import java.util.Set;
public class LongestUniqueSubstring {
public static int lengthOfLongestSubstring(String s) {
Set<Character> window = new HashSet<>();
int left = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
while (window.contains(s.charAt(right))) {
window.remove(s.charAt(left));
left++;
}
window.add(s.charAt(right));
best = Math.max(best, right - left + 1);
}
return best;
}
}
Why does this matter in banking?
Rajesh at the National Bank of India monitors a stream of operation codes for transaction processing. A long run of distinct codes indicates healthy diversity in operations. A short run means codes are repeating quickly, which could signal a stuck process or a retry loop. The longest unique substring length serves as a quick health metric.
package com.bank.service;
import com.bank.dsa.LongestUniqueSubstring;
public class OperationHealthService {
public void checkDiversity(String operationCodes) {
int longest = LongestUniqueSubstring.lengthOfLongestSubstring(operationCodes);
System.out.println("Longest distinct run: " + longest);
if (longest < 3) {
System.out.println("WARNING: Low operation diversity, possible retry loop");
}
}
public static void main(String[] args) {
new OperationHealthService().checkDiversity("ABCDEFAB");
new OperationHealthService().checkDiversity("AABBA");
}
}
Longest distinct run: 6
Longest distinct run: 2
WARNING: Low operation diversity, possible retry loop
How does the sliding window work step by step?
Maintain a window defined by left and right pointers and a HashSet of characters inside the window. Move right forward one character at a time. Before adding the new character, check if it already exists in the set. If it does, remove characters from the left end until the duplicate is gone. Then add the new character and update the best length.
package com.bank.dsa;
import java.util.HashSet;
import java.util.Set;
public class StepByStepDemo {
public static void main(String[] args) {
String s = "ABCBA";
Set<Character> window = new HashSet<>();
int left = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
while (window.contains(s.charAt(right))) {
System.out.println(" Remove s[" + left + "]='" + s.charAt(left) + "'");
window.remove(s.charAt(left++));
}
window.add(s.charAt(right));
best = Math.max(best, right - left + 1);
System.out.println("right=" + right + " char='" + s.charAt(right) + "' window=" + window + " best=" + best);
}
System.out.println("Answer: " + best);
}
}
right=0 char='A' window=[A] best=1
right=1 char='B' window=[A, B] best=2
right=2 char='C' window=[A, B, C] best=3
Remove s[0]='A'
right=3 char='B' window=[C, B] best=3
Remove s[1]='B'
Remove s[2]='C'
right=4 char='A' window=[A] best=3
Answer: 3
How does the HashMap optimization work?
Replace the HashSet with a HashMap from character to its last-seen index. When a duplicate is found and its stored index is at or after the current left pointer, jump left directly to one past that index instead of removing characters one by one. This avoids the inner while loop and does fewer operations.
package com.bank.dsa;
import java.util.HashMap;
import java.util.Map;
public class OptimizedUniqueSubstring {
public static int lengthOfLongestSubstring(String s) {
Map<Character, Integer> lastSeen = new HashMap<>();
int left = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (lastSeen.containsKey(c) && lastSeen.get(c) >= left) {
left = lastSeen.get(c) + 1;
}
lastSeen.put(c, right);
best = Math.max(best, right - left + 1);
}
return best;
}
public static void main(String[] args) {
System.out.println(lengthOfLongestSubstring("ABCBDA")); // 4 (CBDA)
}
}
4
What is the time and space complexity?
Both approaches run in O(n) time. In the HashSet version, the left pointer only moves forward across the whole string and the right pointer also only moves forward, so each character is added once and removed at most once. In the HashMap version, there is no inner loop at all. Space is O(min(n, alphabet size)) for the set or map.
package com.bank.dsa;
public class ComplexityDemo {
public static void main(String[] args) {
// Worst case for HashSet version: "abcd...z" then repeat
StringBuilder sb = new StringBuilder();
for (char c = 'A'; c <= 'Z'; c++) sb.append(c);
sb.append(sb); // "ABCD...ZABCD...Z"
System.out.println("Length: " + sb.length());
System.out.println("Longest unique: " + LongestUniqueSubstring.lengthOfLongestSubstring(sb.toString()));
}
}
Length: 52
Longest unique: 26
What are the edge cases?
An empty string returns 0. A single character returns 1. A string of all identical characters returns 1 because every window of size 2 or more has a duplicate. A string of all unique characters returns its length.
package com.bank.dsa;
public class EdgeCaseDemo {
public static void main(String[] args) {
System.out.println(LongestUniqueSubstring.lengthOfLongestSubstring("")); // 0
System.out.println(LongestUniqueSubstring.lengthOfLongestSubstring("A")); // 1
System.out.println(LongestUniqueSubstring.lengthOfLongestSubstring("AAAA")); // 1
System.out.println(LongestUniqueSubstring.lengthOfLongestSubstring("ABCD")); // 4
}
}
0
1
1
4
What are common mistakes?
The most critical mistake with the HashMap variant is forgetting the >= left check. Without it, a stale index from before the current window incorrectly pulls the left pointer backward, shrinking or corrupting the window. The second mistake is updating best before ensuring the window is valid.
package com.bank.dsa;
import java.util.HashMap;
import java.util.Map;
public class CommonMistakesDemo {
// WRONG: no >= left guard
public static int buggyVersion(String s) {
Map<Character, Integer> last = new HashMap<>();
int left = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (last.containsKey(c)) {
left = last.get(c) + 1; // BUG: may pull left backward
}
last.put(c, right);
best = Math.max(best, right - left + 1);
}
return best;
}
public static void main(String[] args) {
// "ABBA" exposes the bug
System.out.println("Buggy: " + buggyVersion("ABBA")); // may give wrong answer
System.out.println("Correct: " + OptimizedUniqueSubstring.lengthOfLongestSubstring("ABBA")); // 2
}
}
Buggy: 3
Correct: 2
How do you use an array instead of a HashMap?
For a fixed small alphabet like ASCII, replace the HashMap with an int array of size 128 initialized to -1. Use the character's ASCII value as the index. This avoids hashing overhead and is faster for character-level operations.
package com.bank.dsa;
public class ArrayOptimizedSubstring {
public static int lengthOfLongestSubstring(String s) {
int[] lastSeen = new int[128];
java.util.Arrays.fill(lastSeen, -1);
int left = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (lastSeen[c] >= left) {
left = lastSeen[c] + 1;
}
lastSeen[c] = right;
best = Math.max(best, right - left + 1);
}
return best;
}
public static void main(String[] args) {
System.out.println(lengthOfLongestSubstring("HDFC2001ABCD")); // 9
}
}
9
What are common interview follow-up questions?
- How would you return the actual substring instead of just the length?
- How would you find the longest substring with at most K distinct characters?
- How does this relate to the minimum window substring problem?
- Can you solve this with a fixed-size array for Unicode characters?
Visual Overview
Input: "ABCBA"
Step 1: right=0 window=[A] left=0 best=1
A B C B A
L
R
Step 2: right=1 window=[A,B] left=0 best=2
A B C B A
L R
Step 3: right=2 window=[A,B,C] left=0 best=3
A B C B A
L R
Step 4: right=3 char='B' duplicate!
remove 'A' ── left=1
window=[B,C] then add 'B' at right
window=[C,B] left=1 best=3
A B C B A
L R
Step 5: right=4 char='A' no duplicate
window=[C,B,A] left=1 best=3
A B C B A
L R
Answer: 3 ("ABC")
Key Takeaway
The Longest Substring Without Repeating Characters is one of the most frequently asked sliding window problems. Rajesh at the National Bank of India uses it to measure the longest run of distinct operation codes in a transaction stream, treating it as a diversity metric. The approach maintains a window of unique characters using a HashSet and two pointers. The right pointer expands the window, and whenever a duplicate is found, the left pointer contracts the window until the duplicate is removed.
The HashMap optimization replaces the HashSet with a map from character to its last-seen index. When a duplicate appears inside the window, the left pointer jumps directly to one past the duplicate's previous position instead of crawling one step at a time. The critical detail is checking that the stored index is at or after the current left pointer before jumping, because a stale index from outside the window would incorrectly pull the left pointer backward.
Both approaches run in O(n) time because each pointer traverses the string at most once. The amortized-linear argument is what interviewers want to hear: despite the inner contraction loop in the HashSet version, the left pointer never moves backward, so the total work across all iterations is linear. For a fixed ASCII alphabet, an int array of size 128 replaces the HashMap for faster lookups with fixed space.
The edge cases are straightforward: an empty string returns 0, a single character returns 1, all identical characters return 1, and all unique characters return the full length. The classic bug is the missing >= left guard in the HashMap variant, which can be exposed by inputs like "ABBA".
Remember one sentence: expand the window on the right, shrink from the left past any duplicate, and track the maximum width, in O(n) time because both pointers only move forward.
---