No-repeat Substring
Mahabharata — Yudhisthira's Truth Vow — The Longest Unbroken Chain of Unique Truthful Statements
सत्यं वद न पुनः वद — एकवारं उच्चरितम्। दीर्घतमा सत्यमाला यस्मिन् नावृत्तिरस्ति हि॥
*Speak truth, never repeat it — spoken once is sufficient. The longest garland of truth is the one with no repetition.*
The Story
Yudhishthira had taken a solemn vow: he would never repeat himself in the royal court. Every statement he made must be unique — no word-sequence could recur. The court chronicler Sanjaya was tasked with finding the longest stretch of the king's discourse that contained no repeated word-character.
The king's speech was represented as a string of word-symbols: `abcabcbb`.
"The longest unique-character substring," Sanjaya mused. "Starting from the beginning: `abc` — three unique characters. Then the fourth character is 'a', which already appeared! The unique chain breaks."
"If I start fresh from index 1: `bca` — three unique again, then 'b' repeats. Fresh from index 2: `cab` — then 'c' repeats."
The naïve approach was clear: try every possible starting point, extend until a repeat is found. O(n²) time.
"There is a smarter way," said Vidura, who had been watching. "The key observation: when you find a repeated character at position `right`, you don't need to restart from `left+1`. You can jump `left` directly past the PREVIOUS occurrence of the repeated character."
Sanjaya set up the algorithm:
"Maintain a HashMap from character to its most recent index in the string. Maintain a `left` pointer — the start of the current valid window. For each new character `right`:" 1. "If the character was seen before AND its last seen index is ≥ left (meaning it's inside our current window), we must advance left to `lastSeen[char] + 1`. This 'skips over' the previous occurrence." 2. "Update `lastSeen[char] = right`." 3. "Record `right - left + 1` as a candidate maximum."
Sanjaya traced through `abcabcbb`:
- right=0 (a): lastSeen={a:0}. left=0. len=1, max=1 - right=1 (b): lastSeen={a:0,b:1}. left=0. len=2, max=2 - right=2 (c): lastSeen={a:0,b:1,c:2}. left=0. len=3, max=3 - right=3 (a): 'a' last seen at 0, which ≥ left(0)! Jump left to 0+1=1. lastSeen={a:3,...}. len=3, max=3 - right=4 (b): 'b' last seen at 1, which ≥ left(1)! Jump left to 1+1=2. lastSeen={b:4,...}. len=3, max=3 - right=5 (c): 'c' last seen at 2, which ≥ left(2)! Jump left to 2+1=3. lastSeen={c:5,...}. len=3, max=3 - right=6 (b): 'b' last seen at 4, which ≥ left(3)! Jump left to 4+1=5. lastSeen={b:6,...}. len=2, max=3 - right=7 (b): 'b' last seen at 6, which ≥ left(5)! Jump left to 6+1=7. len=1, max=3
Answer: 3 (`abc`, `bca`, or `cab`).
"The crucial nuance," Vidura emphasized, "is the check `lastSeen[char] >= left`. Consider the string `abba`:" - right=0 (a): lastSeen={a:0}. left=0. len=1 - right=1 (b): lastSeen={b:1}. left=0. len=2 - right=2 (b): 'b' last seen at 1 ≥ left(0). Jump left to 2. lastSeen={b:2}. len=1 - right=3 (a): 'a' last seen at 0, but 0 < left(2)! The 'a' at index 0 is OUTSIDE the current window. Don't jump! lastSeen={a:3}. left stays at 2. len=2.
"Without the `≥ left` check, right=3 would incorrectly jump left to 1, shrinking our window even though the previous 'a' was no longer in our window."
Yudhishthira, who had been listening, nodded gravely. "The map remembers all past positions — even those from outside our current window. The check `≥ left` ensures we only react to repetitions WITHIN the current window, not to ancient history."
"Like my vow," the king said. "I do not consider my statements from before my kingship as repetitions of my current speech. Only what I've said in the current session — within the current window — matters."
This is the Sliding Window technique for finding the longest substring without repeating characters.
Sanjaya's First Instinct
For each starting index, extend the substring until a repeat is found. Use a HashSet to track characters in the current window. O(n²) time.
public int lengthOfLongestSubstringBruteForce(String s) {
int max = 0;
for (int start = 0; start < s.length(); start++) {
Set<Character> seen = new HashSet<>();
for (int end = start; end < s.length(); end++) {
char c = s.charAt(end);
if (seen.contains(c)) break; // Repeat found, stop this window
seen.add(c);
max = Math.max(max, end - start + 1);
}
}
return max;
}Vidura's Wisdom
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> lastSeen = new HashMap<>(); // char -> last index
int left = 0;
int maxLen = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
// If char was seen AND is inside current window — must shrink
if (lastSeen.containsKey(c) && lastSeen.get(c) >= left) {
left = lastSeen.get(c) + 1; // Jump past the previous occurrence
}
lastSeen.put(c, right); // Update last seen index
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
// Optimized for ASCII strings using array instead of HashMap
public int lengthOfLongestSubstringOptimized(String s) {
int[] lastSeen = new int[128]; // ASCII characters
Arrays.fill(lastSeen, -1); // -1 means not seen yet
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
int c = s.charAt(right);
if (lastSeen[c] >= left) { // Seen and within window
left = lastSeen[c] + 1;
}
lastSeen[c] = right;
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}Step-by-Step Walkthrough
s = "pwwkew"
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
right=0 (p): lastSeen empty. lastSeen={p:0}. left=0. len=1, max=1
right=1 (w): lastSeen={p:0,w:1}. left=0. len=2, max=2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
right=2 (w): lastSeen[w]=1, 1≥left(0)!
left=1+1=2. lastSeen={w:2}. len=1, max=2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
right=3 (k): lastSeen={...,k:3}. left=2. len=2, max=2
right=4 (e): lastSeen={...,e:4}. left=2. len=3, max=3
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
right=5 (w): lastSeen[w]=2, 2≥left(2)!
left=2+1=3. lastSeen={w:5}. len=3, max=3
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
✅ Return 3 ("wke" at indices 2-4)Deep Insight
**Why store the index instead of just a boolean 'seen'?**
With a boolean set, when we find a repeat, we'd need to walk `left` rightward one step at a time until the repeat is gone — O(n) per repeat, O(n²) total. Storing the last index lets us JUMP `left` in one O(1) operation.
**The `>= left` guard — why it matters:** The `lastSeen` map is never cleared. It retains indices from previous windows. Without `>= left`, we'd incorrectly shrink the window based on a repeat that occurred before our current window started. Example: `abba` — when we process the second 'a', its last seen index is 0 (from before the window moved to left=2). Without the guard, we'd jump left to 1, which is wrong.
**Alternative: sliding window with HashSet (simpler but slower on some inputs):** Use a HashSet; when repeat found, remove `set.remove(s.charAt(left)); left++` one at a time until no repeat. O(n) amortized but with higher constant. The index-map approach is always O(n) with fewer operations.
**Edge cases:** - Empty string: maxLen=0 - All same chars ("aaaa"): maxLen=1 - All distinct chars: maxLen=n
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n²) | O(min(n, alphabet)) | n starting points × up to n extension steps each |
| Optimal | O(n) | O(min(n, alphabet)) | Single pass; map stores at most min(n, 128) entries |
Pattern Recognition
✅ Longest substring without a specific type of repeat ✅ Variable window that shrinks on constraint violation ✅ Storing last-seen INDEX (not just boolean) enables O(1) left-jump ✅ Guard `>= left` to avoid reacting to stale history **LeetCode Trigger Phrases:** → "longest substring without repeating characters" → "no duplicate characters" → "all characters unique" + maximize length
Manusmriti 4.138 (echoed in Gita 17.15)
सत्यं ब्रूयात् प्रियं ब्रूयात् न ब्रूयात् सत्यमप्रियम्। प्रियं च नानृतं ब्रूयात् — एष धर्मः सनातनः॥
Speak truth; speak what is pleasant. Do not speak unpleasant truths. Do not speak pleasant falsehoods. This is the eternal dharma.
Connection: Yudhishthira's vow of non-repetition mirrors the algorithm's invariant: within the current window of speech, no character may repeat. The window advances only when the constraint holds. When a repetition is detected, the king doesn't restart his entire discourse — he wisely skips forward, just as `left` jumps to `lastSeen[char] + 1`. Efficiency in truth-keeping, like in algorithm design, comes from knowing exactly where the previous violation occurred.