In this tutorial, I will demonstrate how to find the longest substring without repeating characters in Java. This is a popular string-based coding interview question that helps you understand the sliding window technique, HashMap, HashSet, and efficient string processing.
A substring is a continuous sequence of characters within a string. The goal is to find the longest continuous section in which every character appears only once.
For example, consider the string "abcabcbb". The longest substring without repeating characters is "abc", which has a length of 3.
You can solve this problem using a brute-force approach, but the sliding window technique is more efficient. In this tutorial, I will explain the sliding window solution using HashMap, an alternative implementation using HashSet, and a straightforward brute-force solution.
1. Problem Statement
Write a Java program to find the longest substring of a given string that contains no repeating characters.
The program should display both the substring and its length.
Example 1
Input: abcabcbb Output: Longest Substring: abc Length: 3
Explanation: The substring "abc" contains three unique characters. Any attempt to extend it introduces a repeated character.
Example 2
Input: bbbbb Output: Longest Substring: b Length: 1
All characters are identical, so the longest substring without repetition contains only one character.
Example 3
Input: pwwkew Output: Longest Substring: wke Length: 3
The substring "wke" contains three unique characters. The sequence "pwke" is not a substring because its characters are not contiguous in the original string.
2. Method 1: Sliding Window Using HashMap
The sliding window technique is one of the most efficient approaches for this problem.
The idea is to maintain a window containing only unique characters. As you move through the string, expand the window when the next character is unique and adjust the starting position when you encounter a duplicate.
A HashMap helps track the most recent index of each character.
How the Sliding Window Technique Works
- Initialize two pointers named
leftandright. - Use a HashMap to store each character's most recent index.
- Move the right pointer through the string.
- If the current character already exists inside the active window, move the left pointer past its previous occurrence.
- Calculate the current window length.
- Update the longest substring when a larger window is found.
Java Program Using HashMap and Sliding Window
import java.util.HashMap;
import java.util.Map;
public class LongestSubstringWithoutRepeating {
/**
* Finds the longest substring without
* repeating characters.
*
* @param str input string
* @return longest substring with unique characters
*/
public static String longestUniqueSubstring(String str) {
if (str == null || str.isEmpty()) {
return "";
}
Map<Character, Integer> lastSeen = new HashMap<>();
int left = 0;
int maxLength = 0;
int startIndex = 0;
for (int right = 0; right < str.length(); right++) {
char currentChar = str.charAt(right);
// Move left if the character repeats
// inside the current window
if (lastSeen.containsKey(currentChar)
&& lastSeen.get(currentChar) >= left) {
left = lastSeen.get(currentChar) + 1;
}
// Store the latest character position
lastSeen.put(currentChar, right);
int currentLength = right - left + 1;
// Update the longest substring
if (currentLength > maxLength) {
maxLength = currentLength;
startIndex = left;
}
}
return str.substring(
startIndex, startIndex + maxLength);
}
public static void main(String[] args) {
String str = "abcabcbb";
String result = longestUniqueSubstring(str);
System.out.println("Input String: " + str);
System.out.println("Longest Substring: " + result);
System.out.println("Length: " + result.length());
}
}Output
Input String: abcabcbb Longest Substring: abc Length: 3
Important: This implementation returns the first longest substring when multiple substrings have the same maximum length. It treats Java char values as characters. A later section explains the distinction between char values and Unicode code points.
3. Step-by-Step Explanation of the Sliding Window Program
Step 1: Handle Null and Empty Strings
if (str == null || str.isEmpty()) {
return "";
}If the input is null or empty, the method returns an empty string.
Step 2: Create a HashMap
Map<Character, Integer> lastSeen = new HashMap<>();The HashMap stores the most recent index at which each character appeared.
For example, after processing the substring "abc", the map contains these logical entries:
a = 0 b = 1 c = 2
HashMap allows the program to locate a previous occurrence efficiently.
Step 3: Initialize the Window Variables
int left = 0;
int maxLength = 0;
int startIndex = 0;leftrepresents the beginning of the active window.maxLengthstores the length of the longest valid substring found so far.startIndexstores the starting position of that longest substring.
Step 4: Traverse the String
for (int right = 0; right < str.length(); right++) {
char currentChar = str.charAt(right);
}The right pointer moves from the beginning to the end of the string.
During each iteration, the program examines one character.
Step 5: Check Whether the Character Repeats
if (lastSeen.containsKey(currentChar)
&& lastSeen.get(currentChar) >= left) {
left = lastSeen.get(currentChar) + 1;
}This is the most important part of the algorithm.
If the current character has appeared inside the active window, the program moves left immediately after that previous occurrence.
For example, suppose the active window contains "abc" and the next character is 'a'.
The character 'a' already exists at index 0, so the program moves left to index 1. The new active window becomes "bca".
The condition lastSeen.get(currentChar) >= left is important because a previously seen character may be outside the current window. In that case, the program should not move the left pointer.
Step 6: Update the Character's Latest Position
lastSeen.put(currentChar, right);The program records the latest index of the current character.
If the character already exists in the HashMap, its previous index is replaced.
Step 7: Calculate the Current Window Length
int currentLength = right - left + 1;This formula calculates how many characters belong to the current window.
For example, if left = 2 and right = 5, the window contains four characters.
Step 8: Update the Longest Substring
if (currentLength > maxLength) {
maxLength = currentLength;
startIndex = left;
}Whenever the current window becomes longer than the best window found so far, the program updates the maximum length and starting index.
Using the > comparison preserves the first substring when multiple longest substrings have equal lengths.
Step 9: Return the Result
return str.substring(
startIndex, startIndex + maxLength);The substring() method extracts the longest valid substring using its starting index and length.
4. Dry Run: Longest Substring Without Repeating Characters
Let's walk through the algorithm using the input:
String: abcabcbb Index: 0 1 2 3 4 5 6 7 Char: a b c a b c b b
The algorithm expands the active window and moves its starting position whenever a character repeats inside that window.
| Right | Character | Left After Update | Current Window | Maximum Length |
|---|---|---|---|---|
| 0 | a | 0 | a | 1 |
| 1 | b | 0 | ab | 2 |
| 2 | c | 0 | abc | 3 |
| 3 | a | 1 | bca | 3 |
| 4 | b | 2 | cab | 3 |
| 5 | c | 3 | abc | 3 |
| 6 | b | 5 | cb | 3 |
| 7 | b | 7 | b | 3 |
The maximum length reaches 3 and never increases beyond that value.
Because the program keeps the first longest substring, it returns "abc".
5. Method 2: Sliding Window Using HashSet
You can also solve this problem using HashSet.
Instead of storing character indexes, a HashSet stores the characters currently present in the active window.
When the next character already exists in the set, the algorithm removes characters from the left side of the window until the duplicate is removed.
Java Program Using HashSet
import java.util.HashSet;
import java.util.Set;
public class LongestSubstringUsingHashSet {
public static String longestUniqueSubstring(String str) {
if (str == null || str.isEmpty()) {
return "";
}
Set<Character> seen = new HashSet<>();
int left = 0;
int maxLength = 0;
int startIndex = 0;
for (int right = 0; right < str.length(); right++) {
char currentChar = str.charAt(right);
// Remove characters until duplicate disappears
while (seen.contains(currentChar)) {
seen.remove(str.charAt(left));
left++;
}
// Add current character to active window
seen.add(currentChar);
int currentLength = right - left + 1;
if (currentLength > maxLength) {
maxLength = currentLength;
startIndex = left;
}
}
return str.substring(
startIndex, startIndex + maxLength);
}
public static void main(String[] args) {
String str = "pwwkew";
String result = longestUniqueSubstring(str);
System.out.println("Input String: " + str);
System.out.println("Longest Substring: " + result);
System.out.println("Length: " + result.length());
}
}Output
Input String: pwwkew Longest Substring: wke Length: 3
How the HashSet Approach Works
The algorithm maintains a HashSet containing all characters in the active window.
- Move the right pointer to the next character.
- If the character is not in the set, add it.
- If the character is already present, remove characters from the left until the duplicate disappears.
- Add the current character and calculate the window length.
- Update the longest substring when necessary.
Although this implementation contains a nested while loop, it still runs in expected linear time.
Each character is added to the set once and removed at most once, so both pointers advance through the string without moving backward.
6. Method 3: Brute-Force Approach
The brute-force approach checks possible substrings until it encounters a repeated character.
For each starting position, the algorithm creates a new HashSet and extends the substring to the right while all characters remain unique.
This method is easy to understand, but it is less efficient than the sliding window technique.
Java Program Using Brute Force
import java.util.HashSet;
import java.util.Set;
public class LongestSubstringBruteForce {
public static String longestUniqueSubstring(String str) {
if (str == null || str.isEmpty()) {
return "";
}
int maxLength = 0;
int startIndex = 0;
for (int i = 0; i < str.length(); i++) {
Set<Character> seen = new HashSet<>();
for (int j = i; j < str.length(); j++) {
char currentChar = str.charAt(j);
// Stop when a repeated character is found
if (!seen.add(currentChar)) {
break;
}
int currentLength = j - i + 1;
if (currentLength > maxLength) {
maxLength = currentLength;
startIndex = i;
}
}
}
return str.substring(
startIndex, startIndex + maxLength);
}
public static void main(String[] args) {
String str = "abcabcbb";
String result = longestUniqueSubstring(str);
System.out.println("Longest Substring: " + result);
System.out.println("Length: " + result.length());
}
}Output
Longest Substring: abc Length: 3
This approach has expected O(n²) time complexity because it may examine many characters from each starting position.
7. Time and Space Complexity
Let's compare the approaches discussed in this tutorial.
| Approach | Expected Time Complexity | Auxiliary Space | Recommendation |
|---|---|---|---|
| Sliding window with HashMap | O(n) | O(k) | Recommended |
| Sliding window with HashSet | O(n) | O(k) | Good alternative |
| Brute force with HashSet | O(n²) | O(k) | Useful for learning |
Here:
nrepresents the length of the string in UTF-16 code units.krepresents the maximum number of distinct characters stored in the HashMap or HashSet.
Why Is Sliding Window O(n)?
In the HashMap approach, the right pointer visits each character once. The left pointer only moves forward when a repeated character appears inside the active window.
In the HashSet approach, characters enter and leave the active window at most once each.
Therefore, both sliding window implementations take expected O(n) time, assuming efficient hash operations.
Space Complexity
The HashMap or HashSet stores characters encountered while processing the string.
The auxiliary space complexity is O(k), where k is the number of distinct character values stored.
Since Java char has a fixed range of values, the number of distinct char keys is bounded. It is still useful to express the space requirement as O(k) when explaining the algorithm.
The returned substring also requires space proportional to its length.
8. Important Edge Cases
Case 1: Empty String
Input: "" Output: Longest Substring: "" Length: 0
The method returns an empty string.
Case 2: Single Character
Input: "a" Output: Longest Substring: a Length: 1
Case 3: All Characters Are Identical
Input: "aaaaa" Output: Longest Substring: a Length: 1
Case 4: All Characters Are Unique
Input: "abcdef" Output: Longest Substring: abcdef Length: 6
When every character is unique, the entire input string is the longest valid substring.
Case 5: Multiple Longest Substrings
Input: "abcdeafgh" Output: Longest Substring: bcdeafgh Length: 8
The longest substring starts after the first 'a', allowing the later 'a' to remain in the window.
Case 6: Uppercase and Lowercase Characters
Input: "aAbBcC" Output: Longest Substring: aAbBcC Length: 6
Java treats uppercase and lowercase character values as different. Therefore, 'a' and 'A' are considered unique.
Case 7: Spaces and Special Characters
Input: "a b!c" Output: Longest Substring: a b!c Length: 5
Spaces and punctuation marks are also characters. They are included in the uniqueness check.
Case 8: Null Input
The implementations in this tutorial return an empty string when the input reference is null.
This behavior is a design choice. In another application, you might prefer to reject null inputs by throwing an IllegalArgumentException.
9. Important Note About Unicode Characters
Java strings use UTF-16 encoding, and the charAt() method returns individual UTF-16 code units.
For ordinary English letters, digits, and many commonly used symbols, the examples in this tutorial work as expected.
However, some Unicode characters, including many emoji, require two Java char values called a surrogate pair.
Therefore, a solution based on charAt() does not always treat a supplementary Unicode character as one character.
If your application must support arbitrary Unicode code points, consider processing the string using codePoints() and tracking integer code points instead.
For most introductory coding interview problems that use ASCII characters, the char-based sliding window implementation is sufficient.
10. Common Mistakes to Avoid
Mistake 1: Confusing Substring and Subsequence
A substring must contain consecutive characters from the original string.
A subsequence may skip characters.
For example, "pwke" is not a substring of "pwwkew" because the characters are not consecutive.
Mistake 2: Moving the Left Pointer Backward
When using HashMap, do not move the left pointer backward if a character's previous occurrence lies outside the current window.
Always check whether its previous index is greater than or equal to the current left pointer.
Mistake 3: Forgetting to Update Character Positions
After processing the current character, update its most recent index in the HashMap.
Otherwise, later duplicate checks may use an outdated position.
Mistake 4: Updating Only the Maximum Length
If the problem asks you to return the actual substring, storing only the maximum length is not enough.
You must also track where the longest valid substring begins.
Mistake 5: Using a Nested Loop Without Understanding Complexity
The brute-force approach is useful for understanding the problem, but it may perform repeated comparisons for overlapping substrings.
The sliding window technique avoids this repeated work and is generally the better choice for large strings.
11. Frequently Asked Questions
Q1. What is the longest substring without repeating characters?
It is the longest continuous portion of a string in which each character appears only once.
Q2. What is the best approach to solve this problem in Java?
The sliding window technique is generally the preferred approach. It finds the result in expected O(n) time.
Q3. Can I solve this problem using HashMap?
Yes. HashMap stores the most recent index of each character, allowing the algorithm to move the left boundary directly when a duplicate appears.
Q4. Can I solve this problem using HashSet?
Yes. HashSet tracks characters in the active window. When a duplicate appears, the algorithm removes characters from the left until the window becomes valid again.
Q5. What is the time complexity of the sliding window approach?
The expected time complexity is O(n), where n represents the string length.
Q6. What happens when all characters are the same?
The longest substring has length 1 because any two consecutive characters repeat the same value.
Q7. What happens when every character is unique?
The entire string becomes the longest substring without repeating characters.
Q8. Does the algorithm return the first longest substring?
Yes. The examples update the result only when a strictly longer substring is found. When several longest substrings have the same length, the first one is retained.
Q9. Is this problem related to the sliding window technique?
Yes. It is one of the classic sliding window interview problems because it maintains a valid range of consecutive elements while adjusting its boundaries.
12. Conclusion
In this tutorial, you learned how to find the longest substring without repeating characters in Java using three different approaches.
- Sliding window with HashMap: Tracks the latest index of each character and moves the left boundary efficiently.
- Sliding window with HashSet: Maintains unique characters within the active window.
- Brute-force approach: Examines possible substrings and helps explain the basic logic.
For Java coding interviews, I recommend practicing the sliding window with HashMap approach. It solves the problem in expected linear time and demonstrates an important algorithmic technique.
Once you understand this pattern, you can apply it to other interview problems involving longest substrings, distinct elements, character frequencies, and fixed-size or variable-size windows.
13. Official Java Documentation
For more information about the Java APIs used in this tutorial, refer to the official Oracle documentation:
- Java String Class — Documentation for
charAt(),length(),substring(), andcodePoints(). - Java HashMap Class — Documentation for storing and retrieving character indexes.
- Java HashSet Class — Documentation for storing unique elements.
- Java Map Interface — Documentation for
containsKey(),get(), andput(). - Java Character Class — Documentation for Java characters and Unicode-related operations.
Continue Learning with Java Guides
Want to take your programming skills to the next level? Explore my practical Udemy courses on Java, Spring Boot, Microservices, Full-Stack Development, Docker, and Generative AI. You can also follow my structured learning roadmaps to become a professional developer.
By Ramesh Fadatare - Udemy Instructor Partner
Comments
Post a Comment
Leave Comment