Definition
- No-repeat substring – finds the length of the longest contiguous substring where every character appears exactly once.
- Variable-size sliding window – a right pointer expands the window one character at a time, and the left boundary jumps forward when a duplicate is detected.
- Last-seen map – a HashMap or index array stores the most recent position of each character for O(1) duplicate detection.
- Jump rule – when the current character was last seen at position
lastandlast >= left, setleft = last + 1to exclude the duplicate. - Time O(n), space O(k) – each character is visited at most twice (once by each pointer), and the map is bounded by alphabet size k.
At the National Bank of India, Rajesh scans a tape of transaction-channel codes looking for the longest stretch where no channel repeats. He slides a highlighter rightward, and the moment a channel he already highlighted shows up again, he lifts the left edge forward past the previous occurrence, always remembering the longest clean stretch he has seen.
Understanding the Concepts
What is the No-Repeat Substring problem?
The problem asks for the length of the longest contiguous substring within a given string where every character is distinct. For example, in "ABCABCBB", the longest substring without repeating characters is "ABC" with length 3. In "PWWKEW", it is "WKE" with length 3.
package com.bank.core;
// Input: "TRANSFERPAY"
// Substrings with all unique chars: "TRANSFE", "RANSFEP", "ANSFERP", ...
// Longest: "TRANSFE" or "ANSFERPAY" depends on actual duplicates
Why use a sliding window?
The brute-force approach checks every substring and tests for uniqueness, giving O(n^3) time with a set check or O(n^2) with precomputation. The sliding window reduces this to O(n) by maintaining a window that is always duplicate-free. The key insight is that when a duplicate enters, we do not need to restart from scratch: we just move the left boundary past the previous occurrence of the duplicated character.
package com.bank.core;
// Brute force: O(n^3) - check every substring for uniqueness
// Optimized brute force: O(n^2) with set per window
// Sliding window: O(n) - each character visited at most twice
How does the sliding window work?
You maintain a left boundary and a right pointer. A map stores the index of each character's most recent appearance. As the right pointer moves to each character, you check the map. If the character was last seen at a position at or after the left boundary, it is a duplicate inside the window, so you move the left boundary to one past that position. Then you update the character's position in the map and compute the current window length.
package com.bank.service;
import java.util.HashMap;
import java.util.Map;
public class NoRepeatSubstring {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> lastSeen = new HashMap<>();
int left = 0;
int best = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
int last = lastSeen.getOrDefault(c, -1);
if (last >= left) {
left = last + 1; // jump past the duplicate
}
lastSeen.put(c, right);
best = Math.max(best, right - left + 1);
}
return best;
}
public static void main(String[] args) {
NoRepeatSubstring solver = new NoRepeatSubstring();
System.out.println(solver.lengthOfLongestSubstring("ABCABCBB"));
System.out.println(solver.lengthOfLongestSubstring("BBBBB"));
System.out.println(solver.lengthOfLongestSubstring("PWWKEW"));
}
}
3
1
3
Why is the guard condition last >= left critical?
The map may contain stale entries for characters that were once in the window but are now to the left of the current left boundary. Without the guard last >= left, the left boundary could jump backward to an old position, which would make the window contain duplicates from a previous iteration. The guard ensures we only react to duplicates that are actually inside the current window.
package com.bank.core;
// Example: s = "ABBA"
// right=0, c='A', last=-1, left stays 0, window "A"
// right=1, c='B', last=-1, left stays 0, window "AB"
// right=2, c='B', last=1, 1>=0, left=2, window "B"
// right=3, c='A', last=0, 0 < 2 (stale!), left stays 2, window "BA"
// Without guard: left would jump to 0+1=1, making window "BBA" with duplicate B!
How do you use an int array instead of a HashMap?
For ASCII input, an int[128] array indexed by character value is faster than a HashMap because it avoids boxing, hashing, and collision resolution. Initialize all entries to -1 to indicate no character has been seen.
package com.bank.service;
public class NoRepeatSubstringFast {
public int lengthOfLongestSubstring(String s) {
int[] lastSeen = new int[128];
java.util.Arrays.fill(lastSeen, -1);
int left = 0;
int 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;
}
}
What are the edge cases?
Edge cases include: an empty string returns 0, a string of all identical characters returns 1, a string with all unique characters returns the full length, and a single character returns 1.
package com.bank.core;
// Edge case 1: "" -> 0 (empty string)
// Edge case 2: "AAAA" -> 1 (all same characters)
// Edge case 3: "ABCDEF" -> 6 (all unique)
// Edge case 4: "A" -> 1 (single character)
// Edge case 5: "AU" -> 2 (two unique characters)
What about a banking use case?
At the National Bank of India, each customer session records an ordered sequence of transaction-channel codes. The fraud-analytics team measures the longest continuous stretch where no channel repeats, because a long diverse-channel run is a stable behavioral fingerprint. A sudden drop signals possible account takeover.
package com.bank.service;
public class FraudChannelAnalyzer {
private final NoRepeatSubstring solver = new NoRepeatSubstring();
public int longestDiverseStretch(String channelSequence) {
return solver.lengthOfLongestSubstring(channelSequence);
}
public static void main(String[] args) {
FraudChannelAnalyzer analyzer = new FraudChannelAnalyzer();
String normalSession = "AUNWMCPT"; // ATM, UPI, NEFT, Web, Mobile, Cheque, POS, Transfer
String suspiciousSession = "AAUUMM";
System.out.println("Normal diverse stretch: "
+ analyzer.longestDiverseStretch(normalSession));
System.out.println("Suspicious diverse stretch: "
+ analyzer.longestDiverseStretch(suspiciousSession));
}
}
Normal diverse stretch: 8
Suspicious diverse stretch: 2
What are common mistakes?
The most common mistake is forgetting the last >= left guard, which causes the left boundary to jump backward on stale map entries. Another mistake is using a set instead of a map, which requires an inner loop to remove characters one by one from the left, turning the solution into O(2n) instead of O(n) with direct jumps.
package com.bank.core;
// WRONG: using a set with inner removal loop
Set<Character> set = new HashSet<>();
while (set.contains(s.charAt(right))) {
set.remove(s.charAt(left));
left++; // O(n) inner loop in worst case
}
// Still correct but slower: O(2n) vs O(n) with direct jump
// CORRECT: direct jump using map
int last = lastSeen.getOrDefault(c, -1);
if (last >= left) left = last + 1; // O(1) jump
What should a senior engineer know?
A senior engineer should recognize this as the canonical variable-size sliding window problem. The same template applies to many string problems: longest substring with at most k distinct characters, longest substring with at most k replacements, and minimum window substring. The key difference between them is only the window validity condition.
For production use on very long strings, the int[128] array version avoids HashMap overhead and is measurably faster. The space is always O(alphabet size), not O(n).
package com.bank.core;
// This is the canonical variable-size sliding window:
// 1. Expand right pointer
// 2. Check/update window state
// 3. Shrink left boundary if window invalid
// 4. Record best window
// Same template for: at-most-k-distinct, min-window-substring, etc.
Visual Overview
Sliding window on s = "ABCBAD":
Step-by-step:
right=0: c='A', last=-1, left=0
┌───┐
│ A │ B C B A D window="A", best=1
└───┘
right=1: c='B', last=-1, left=0
┌───────┐
│ A B │ C B A D window="AB", best=2
└───────┘
right=2: c='C', last=-1, left=0
┌───────────┐
│ A B C │ B A D window="ABC", best=3
└───────────┘
right=3: c='B', last=1, 1>=0 -> left=2
┌───────┐
A B │ C B │ A D window="CB", best=3
└───────┘
right=4: c='A', last=0, 0<2 (stale!) -> left stays 2
┌───────────┐
A B │ C B A │ D window="CBA", best=3
└───────────┘
right=5: c='D', last=-1, left=2
┌───────────────┐
A B │ C B A D │ window="CBAD", best=4
└───────────────┘
Answer: 4
Key: the stale entry for 'A' at index 0 is ignored
because 0 < left(2), preventing a backward jump.
Key Takeaway
The no-repeat substring problem asks for the length of the longest contiguous substring that contains no repeated character. You solve it with a variable-size sliding window in linear time. A left boundary, a right pointer scanning forward, and a map from each character to its last-seen index are all you need. As the right pointer moves over each character, you check the map: if the character was last seen at or after the current left boundary, it is a duplicate inside the window, so you jump the left boundary past the previous occurrence.
The single most important detail is the guard condition last >= left. Without it, stale map entries for characters that already fell out of the window would drag the left boundary backward, introducing duplicates. Comparing against the live left boundary keeps the algorithm correct. Because the right pointer advances n times and the left pointer only ever moves forward, the total work is O(n).
For production use on long strings, replacing the HashMap with an int[128] index array for ASCII input eliminates boxing and hashing overhead, cutting constant factors significantly. The space is always bounded by the alphabet size, not the input length, so it is effectively O(1) for a fixed character set.
At the National Bank of India, the fraud-analytics team applied this on customer session channel sequences to measure the longest diverse-channel stretch as a behavioral fingerprint. A sudden drop in that length signaled possible account takeover. The linear sliding window processed millions of sessions in the nightly batch, and the same template generalized to other window problems across the analytics pipeline.
Remember one sentence: expand right, jump left past any duplicate's last position guarded by the left boundary, and track the longest all-distinct window.
---