LeetCode Problem 3, titled “Longest Substring Without Repeating Characters,” is a popular coding challenge that involves finding the length of the longest substring without repeating characters in a given string.
Problem Statement
Given a string s
, find the length of the longest substring without repeating characters.
Example:
Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.
Approach
To solve this problem, we’ll use a sliding window technique. We’ll maintain a window that contains non-repeating characters and slide it to the right. If we encounter a repeating character, we’ll adjust the window accordingly.
Steps:
- Initialize a variable
maxLength
to keep track of the maximum length of the substring without repeating characters. - Initialize a HashMap to store the index of the last occurrence of each character in the string.
- Initialize two pointers,
left
andright
, to represent the boundaries of the current substring. - Iterate over the string using the
right
pointer:
- If the character at
s[right]
is not in the HashMap or its last occurrence is beforeleft
, it means it’s a non-repeating character. In this case, we updatemaxLength
and move theright
pointer to the next character. - If the character is already in the HashMap and its last occurrence is after
left
, it means it’s a repeating character. We updateleft
to the index after the last occurrence of this character.
- Continue this process until the
right
pointer reaches the end of the string. - Return
maxLength
.
Java Solution
import java.util.HashMap; public class LongestSubstring { public int lengthOfLongestSubstring(String s) { int maxLength = 0; HashMap<Character, Integer> charIndexMap = new HashMap<>(); int left = 0; for (int right = 0; right < s.length(); right++) { char currentChar = s.charAt(right); if (charIndexMap.containsKey(currentChar) && charIndexMap.get(currentChar) >= left) { left = charIndexMap.get(currentChar) + 1; } charIndexMap.put(currentChar, right); maxLength = Math.max(maxLength, right - left + 1); } return maxLength; } }
Python Solution
def length_of_longest_substring(s): max_length = 0 char_index_map = {} left = 0 for right in range(len(s)): current_char = s[right] if current_char in char_index_map and char_index_map[current_char] >= left: left = char_index_map[current_char] + 1 char_index_map[current_char] = right max_length = max(max_length, right - left + 1) return max_length
Conclusion
The Longest Substring Without Repeating Characters problem is a classic example of using the sliding window technique. The provided solutions in both Java and Python should efficiently solve this problem for various test cases. This approach has a time complexity of O(n), where n is the length of the input string s
.