Definition
- Last-seen map stores a
HashMapfrom each character to the index where it was most recently seen. - Jump optimization moves the left pointer directly to
lastSeen.get(c) + 1when a duplicate is found inside the window, avoiding the inner removal loop. - At-least-left guard checks
lastSeen.get(c) >= leftbefore jumping, to avoid using stale indices from outside the window. - O(n) time because the right pointer traverses once and the left pointer only moves forward.
- O(min(n, alphabet)) space for the character-to-index map.
Rajesh at the National Bank of India scans session tokens and keeps a notebook recording where he last saw each character. When a repeat appears inside his current window, he flips to that notebook entry and jumps his left pointer to one past that previous position. He does not erase entries one by one; he jumps directly.
Understanding the Concepts
What is the problem?
Given a string, find the length of the longest contiguous substring that contains no repeated character. This is the same problem as Q1445 but solved with a HashMap optimization that avoids the inner while loop for removing characters from the window.
package com.bank.dsa;
import java.util.HashMap;
import java.util.Map;
public class LongestUniqueHashMap {
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;
}
}
Why use HashMap instead of HashSet?
The HashSet version uses an inner while loop to remove characters from the left until the duplicate is gone. The HashMap version stores the index of each character's last occurrence, allowing the left pointer to jump directly to one past that index in a single operation. Both are O(n) amortized, but the HashMap version does fewer operations per step.
package com.bank.dsa;
public class SetVsMapDemo {
public static void main(String[] args) {
String s = "ABCBDA";
// HashSet version: inner while loop removes A, B before adding B again
// HashMap version: jumps left directly to index 2 (one past previous B)
System.out.println("HashSet: " + LongestUniqueSubstring.lengthOfLongestSubstring(s));
System.out.println("HashMap: " + LongestUniqueHashMap.lengthOfLongestSubstring(s));
}
}
HashSet: 4
HashMap: 4
Why is the at-least-left guard critical?
Without the guard lastSeen.get(c) >= left, a character seen before the current window would incorrectly pull the left pointer backward. For example, in "ABBA", after processing the second B, left moves to index 2. When processing the second A, the stored index for A is 0, which is before left. Jumping to index 1 would be moving backward, corrupting the window.
package com.bank.dsa;
import java.util.HashMap;
import java.util.Map;
public class GuardDemo {
// WRONG: no >= left guard
public static int buggy(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 move left backward!
}
last.put(c, right);
best = Math.max(best, right - left + 1);
}
return best;
}
public static void main(String[] args) {
System.out.println("Buggy ABBA: " + buggy("ABBA")); // 3 (wrong!)
System.out.println("Correct ABBA: " + LongestUniqueHashMap.lengthOfLongestSubstring("ABBA")); // 2
}
}
Buggy ABBA: 3
Correct ABBA: 2
How does the algorithm trace through ABBA?
Walking through "ABBA" step by step shows why the guard matters:
package com.bank.dsa;
import java.util.HashMap;
import java.util.Map;
public class TraceDemo {
public static void main(String[] args) {
String s = "ABBA";
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) && last.get(c) >= left) {
left = last.get(c) + 1;
}
last.put(c, right);
best = Math.max(best, right - left + 1);
System.out.println("right=" + right + " c=" + c + " left=" + left + " best=" + best + " last=" + last);
}
}
}
right=0 c=A left=0 best=1 last={A=0}
right=1 c=B left=0 best=2 last={A=0, B=1}
right=2 c=B left=2 best=2 last={A=0, B=2}
right=3 c=A left=2 best=2 last={A=3, B=2}
How do you use an array instead of HashMap?
For ASCII characters, replace the HashMap with an int array of size 128 initialized to -1. The character's ASCII value serves as the index. This avoids hashing overhead and gives constant-time lookups with fixed memory.
package com.bank.dsa;
import java.util.Arrays;
public class ArrayOptimized {
public static int lengthOfLongestSubstring(String s) {
int[] lastSeen = new int[128];
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 the edge cases?
An empty string returns 0. A single character returns 1. All identical characters return 1. All unique characters return the full length. The at-least-left guard correctly handles all these cases.
package com.bank.dsa;
public class EdgeCaseDemo {
public static void main(String[] args) {
System.out.println(LongestUniqueHashMap.lengthOfLongestSubstring("")); // 0
System.out.println(LongestUniqueHashMap.lengthOfLongestSubstring("A")); // 1
System.out.println(LongestUniqueHashMap.lengthOfLongestSubstring("AAAA")); // 1
System.out.println(LongestUniqueHashMap.lengthOfLongestSubstring("ABCD")); // 4
}
}
0
1
1
4
What is the time and space complexity?
Time is O(n) because the right pointer visits each character once and the left pointer only moves forward. There is no inner loop. Space is O(min(n, alphabet size)) for the HashMap, or O(1) with the fixed-size array for ASCII.
What are common interview follow-up questions?
- How would you return the actual substring instead of the length?
- How would you find the longest substring with at most K distinct characters?
- What if the input contains Unicode characters beyond ASCII?
- How does this compare to the HashSet sliding window approach?
Visual Overview
Input: "ABBA"
HashMap: {character -> last seen index}
right=0 c='A' lastSeen={A:0} left=0 window="A" best=1
right=1 c='B' lastSeen={A:0,B:1} left=0 window="AB" best=2
right=2 c='B' B seen at 1, 1 >= left(0)
left = 1+1 = 2
lastSeen={A:0,B:2} window="B" best=2
right=3 c='A' A seen at 0, but 0 < left(2)
STALE ── do NOT jump!
lastSeen={A:3,B:2} window="BA" best=2
Answer: 2
┌─────────────────────────────────────────┐
│ Without guard: left would jump to 1 │
│ (backward!), giving wrong answer 3 │
│ │
│ With guard: stale index ignored, │
│ left stays at 2, correct answer 2 │
└─────────────────────────────────────────┘
Key Takeaway
The HashMap variant of the Longest Substring Without Repeating Characters is the optimized version that eliminates the inner removal loop. Instead of removing characters one by one from the left, Rajesh at the National Bank of India keeps a map from each character to its last-seen index and jumps the left pointer directly to one past the duplicate's previous position.
The correctness detail that makes or breaks this solution is the at-least-left guard: before jumping, check that the stored previous index is at or after the current left pointer. A character might have been seen earlier but already fallen outside the window, and blindly moving left to that stale index would pull the pointer backward, corrupting the window. The input "ABBA" is the classic test case that exposes this bug.
Both the HashSet and HashMap versions run in O(n) time because each pointer traverses the string at most once. The HashMap version does fewer operations per step because it avoids the inner removal loop. For a fixed ASCII alphabet, an int array of size 128 initialized to -1 replaces the HashMap for even faster lookups.
In the banking domain, this algorithm serves as a quick entropy heuristic for session tokens: a long run of distinct characters indicates good diversity, while a short run suggests weak randomness worth flagging. The HashMap version is preferred for arbitrary character sets, while the array version is ideal for ASCII-only tokens.
Remember one sentence: store each character's last-seen index, jump left past duplicates, and always check that the stored index is within the current window before jumping.
---