The “Longest Substring Without Repeating Characters” is a popular problem on platforms like LeetCode. This problem tests your understanding of sliding window techniques, hash-based lookups, and efficient string manipulation. Here’s a step-by-step framework to learn, practice, and master this problem:
Understanding the Problem
You are given a string s. The goal is to determine the length of the longest substring that contains no repeating characters. A substring is defined as a contiguous block of characters within the string.
What is a Substring?
• A substring is a sequence of characters within a string where all the characters are contiguous. For example, in the string “abcde”, “abc”, “cde”, and “bcd” are all substrings, while “ace” is not.
Example
• Input: “abcabcbb”
• Explanation:
• Start with the substring “abc”, which has no repeated characters.
• After “abc”, the next character (“a”) is a repeat, so you need to move past the previous occurrence of “a”.
• The longest substring without repeating characters is “abc”, with a length of 3.
• Output: 3
Brute Force Approach
The brute force approach systematically checks all possible substrings to find the longest one without repeating characters.
Steps:
1. Generate All Substrings:
• Start with every possible character as the beginning of a substring.
• Extend the substring one character at a time until the end of the string.
2. Check Uniqueness:
• For each substring, ensure all characters are unique.
• Use a data structure like a Set to track characters.
3. Track the Longest Substring:
• Keep a variable to store the maximum length of all unique substrings encountered.
class Solution {
public int lengthOfLongestSubstring(String s) {
int maxLength = 0;
for (int i = 0; i < s.length(); i++) {
for (int j = i + 1; j <= s.length(); j++) {
if (areAllCharactersUnique(s.substring(i, j))) {
maxLength = Math.max(maxLength, j - i);
}
}
}
return maxLength;
}
private boolean areAllCharactersUnique(String substring) {
Set<Character> set = new HashSet<>();
for (char c : substring.toCharArray()) {
if (set.contains(c)) return false;
set.add(c);
}
return true;
}
}Time and Space Complexity
• Time Complexity: O(n^3)
• Generating all substrings: O(n^2).
• Checking uniqueness for each substring: O(n).
• Space Complexity: O(k)
• Additional space is required for the Set used to check uniqueness, where k is the substring length.
Optimized Approach: Sliding Window With Set
The sliding window technique is a powerful method to solve problems involving substrings or subarrays. For the “Longest Substring Without Repeating Characters” problem, this approach optimizes performance by dynamically adjusting the substring boundaries. Let’s dive into how this method works, its implementation, and why it’s a significant improvement over brute force.
Instead of generating all substrings and checking for duplicates, the sliding window approach dynamically adjusts the range of the substring using two pointers: left and right.
Steps:
1. Define the Sliding Window:
• The window starts as empty, defined by two pointers: left (starting position) and right (current character position).
2. Use a Set for Tracking:
• A Set is used to track characters within the window to ensure uniqueness.
3. Expand the Window:
• Move the right pointer to include a new character. If the character is unique within the window, continue expanding.
4. Shrink the Window When Duplicates Are Found:
• If a duplicate character is encountered, move the left pointer forward until the duplicate is removed.
5. Update Maximum Length:
• At each step, calculate the current window length (right – left + 1) and update the maximum length.
import java.util.HashSet;
import java.util.Set;
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> window = new HashSet<>();
int left = 0, maxLength = 0;
for (int right = 0; right < s.length(); right++) {
char current = s.charAt(right);
// Shrink the window until the duplicate is removed
while (window.contains(current)) {
window.remove(s.charAt(left));
left++;
}
// Add the current character to the window
window.add(current);
// Update the maximum length
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
}
• The sliding window approach eliminates redundant checks, significantly improving performance compared to brute force.
Optimized Approach: Sliding Window with Hash Map
Instead of only tracking the characters currently in the window (as in the basic sliding window approach), this technique uses a hash map to store the last occurrence index of each character. This enables us to jump directly to the next valid position when duplicates are found, skipping unnecessary checks.
import java.util.HashMap;
class Solution {
public int lengthOfLongestSubstring(String s) {
HashMap<Character, Integer> charIndexMap = new HashMap<>();
int maxLength = 0;
int left = 0;
for (int right = 0; right < s.length(); right++) {
char current = s.charAt(right);
// If the character is a duplicate, move the left pointer
if (charIndexMap.containsKey(current)) {
left = Math.max(left, charIndexMap.get(current) + 1);
}
// Update the character's index in the map
charIndexMap.put(current, right);
// Update the maximum length
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
}Steps:
1. Initialize Variables:
• Use two pointers, left and right, to define the sliding window.
• Use a HashMap to store the last index of each character in the string.
• Maintain a variable maxLength to track the length of the longest substring.
2. Expand the Window:
• Move the right pointer to iterate over the string.
3. Handle Duplicates:
• If the character at right is already in the hash map:
• Move the left pointer to the index after the last occurrence of the duplicate character (ensuring no overlap in the substring).
4. Update Maximum Length:
• At each step, calculate the length of the current window (right – left + 1) and update maxLength if it’s greater.
5. Update the Hash Map:
• Store the current index of the character in the hash map.
Why Hashmap Solution is Better
When solving the “Longest Substring Without Repeating Characters” problem, the HashMap-based sliding window algorithm emerges as the most efficient and optimized approach. By leveraging a hash map to track the last occurrence index of each character, this algorithm minimizes redundant operations and handles duplicates with precision.
The HashMap algorithm uses the last occurrence index of each character to handle duplicates. Instead of shrinking the window one character at a time (like the HashSet approach), it jumps the left pointer directly to the next valid position, saving unnecessary operations.
Example: “abcabcbb”
• HashSet Approach:
• On encountering the second “a”, the left pointer moves from 0 to 1 by removing characters one by one.
• This involves redundant operations.
• HashMap Approach:
• On encountering the second “a” at index 3, the left pointer jumps directly to 1 (index after the previous “a” at 0).
• Saves unnecessary removals and recalculations.
Time and Space Complexity
• Time Complexity: O(n)
• Each character is added to or updated in the hash map at most once, making the algorithm linear.
• Space Complexity: O(k)
• The hash map stores up to k unique characters in the string, where k is the size of the character set (e.g., ASCII or Unicode).
Key Takeaways
• Efficiency Matters: The hash map approach optimizes performance by minimizing redundant checks.
• Powerful Pattern: This approach can be adapted for other substring problems involving character constraints.
• Focus on Edge Cases: Always test edge cases like empty strings or repetitive characters.
By mastering this technique, you’ll be well-equipped to handle not only the “Longest Substring Without Repeating Characters” problem but also a wide range of substring and sliding window challenges.
