Longest Substring Without Repeating Characters Java | Fresher Interview
Fast recall
Quick revision
Core answer
HashSet tracking characters in the window. Expand right to add characters; on a duplicate, shrink from the left until it's gone. Track the maximum window size. This runs in O(n) time and O(min(n, m)) space, where m is the alphabet size.Can you implement the variable-size sliding window with HashSet-based duplicate detection and proper expand/contract logic
Using nested loops to check every substring for duplicates, giving O(n^2) or O(n^3) instead of the two-pointer pattern
Mention the HashMap optimization storing each character's last index, letting left jump directly past the previous occurrence
Interview-ready guide
Interview answer
To find the longest substring without repeating characters, I'd use a variable-size sliding window with a HashSet.
I have two pointers, left and right, both starting at zero. The HashSet tracks the characters currently in the window between left and right. I move the right pointer forward through the string, adding each character to the set.
Before adding, I check if the character is already in the set. If it is, that means I have a duplicate, so the window is invalid. I then enter a while loop that shrinks the window from the left.
In each iteration, I remove the character at the left pointer from the set and move left forward. This continues until the duplicate is gone and the set no longer contains the character at right. Once the window is valid again, I add the character at right to the set and calculate the window size as right minus left plus one.
I track the maximum window size I've seen and return it at the end. The time complexity is O of n because even though there's a while loop inside a for loop, each character enters the set once and leaves once. The worst case is two n operations.
The space complexity is O of the alphabet size, which is at most one twenty eight for ASCII or twenty six for lowercase English. A more advanced optimization uses a HashMap to store the most recent index of each character. When you find a duplicate, instead of shrinking one character at a time, you can jump the left pointer directly to the position right after the previous occurrence.
Longest Substring Without Repeating Characters Java | Fresher Interview
Direct Answer
Use a variable-size sliding window with a HashSet tracking characters in the window. Expand right to add characters; on a duplicate, shrink from the left until it's gone. Track the maximum window size. This runs in O(n) time and O(min(n, m)) space, where m is the alphabet size.
Deep Dive & Architecture
Maintain a window [left, right] with no repeated characters. A map stores the most recent index of each character. When the current character already appears inside the window, move left to one position after that old index.
Worked example: abba
At indexes 0 and 1, the window is ab and the best length is 2. At index 2, b was last seen at 1, so move left to 2; the valid window becomes b. At index 3, a was last seen at 0, which is already outside the current window. Left must stay at 2, producing ba and preserving the best length 2.
That last step is why the update is left = max(left, lastIndex + 1). Moving left backward would reintroduce an invalid part of the string.
Each right index is processed once and left only moves forward, so time is O(n). The map uses O(k) space for the distinct characters. A set-based version also works but may remove characters one at a time; the last-index map jumps directly.
Java char iteration is fine for common interview inputs. If full Unicode symbols matter, process code points and define indexes accordingly.
Code Example
import java.util.HashSet;
import java.util.Set;
public class LongestSubstringUnique {
public static int lengthOfLongestSubstring(String s) {
Set<Character> window = new HashSet<>();
int left = 0, maxLength = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
while (window.contains(c)) { // shrink until duplicate removed
window.remove(s.charAt(left));
left++;
}
window.add(c); // expand
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
public static void main(String[] args) {
System.out.println(lengthOfLongestSubstring("abcabcbb")); // 3 ("abc")
}
}
Common Mistakes & Pitfalls
- Nested loops checking every substring: generating all substrings and testing each is O(n^2) or O(n^3). Use two pointers in one pass.
- Not removing characters when shrinking: you must remove
s.charAt(left)before incrementingleft, otherwise the while loop never exits. - Wrong window size: the window is
[left, right]inclusive, so the size isright - left + 1, notright - left.
Check your understanding
Answer these without looking back at the article.
- What is the sliding window technique and when do you use it?
- How do you find the maximum sum subarray of size k?
- How do you find all anagrams of a pattern in a string?
Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.