LeetCode problem 3#: Longest Substring Without Repeating Characters solution

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:

1. Initialize a variable maxLength to keep track of the maximum length of the substring without repeating characters.
2. Initialize a HashMap to store the index of the last occurrence of each character in the string.
3. Initialize two pointers, left and right, to represent the boundaries of the current substring.
4. Iterate over the string using the right pointer:

• If the character at s[right] is not in the HashMap or its last occurrence is before left, it means it’s a non-repeating character. In this case, we update maxLength and move the right 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 update left to the index after the last occurrence of this character.

1. Continue this process until the right pointer reaches the end of the string.
2. 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.