DevExCode

LeetCode 3: Longest Substring Without Repeating Characters Solution

Master LeetCode problem 3 (Longest Substring Without Repeating Characters), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

3. Longest Substring Without Repeating Characters

Medium
Hash TableStringSliding Window

Problem Explanation

Explanation:

To solve this problem, we can use the sliding window technique. We maintain a window that contains characters without repeating characters. We iterate through the string, keep track of the characters we have seen so far using a hashmap to store the index of the characters. If we encounter a character that is already in the window, we update the start index of the window to the next index of the repeated character. We update the maximum length of the substring as we iterate through the string.

  1. Initialize a hashmap to store characters and their indices.
  2. Initialize variables for the start index of the window, the maximum length of the substring, and the current index.
  3. Iterate through the string:
    • Check if the character is in the hashmap and if its index is within the current window.
      • If yes, update the start index of the window to the next index of the repeated character.
    • Update the current character's index in the hashmap.
    • Update the maximum length of the substring.
  4. Return the maximum length of the substring.

Time Complexity: O(n) where n is the length of the input string. Space Complexity: O(min(n, m)) where n is the length of the input string and m is the size of the character set.

:

Solution Code

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        Map<Character, Integer> charIndexMap = new HashMap<>();
        int maxLength = 0;
        int start = 0;
        
        for (int end = 0; end < s.length(); end++) {
            char c = s.charAt(end);
            if (charIndexMap.containsKey(c) && charIndexMap.get(c) >= start) {
                start = charIndexMap.get(c) + 1;
            }
            charIndexMap.put(c, end);
            maxLength = Math.max(maxLength, end - start + 1);
        }
        
        return maxLength;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 3 (Longest Substring Without Repeating Characters)?

This page provides optimized solutions for LeetCode problem 3 (Longest Substring Without Repeating Characters) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 3 (Longest Substring Without Repeating Characters)?

The time complexity for LeetCode 3 (Longest Substring Without Repeating Characters) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 3 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3 in Java, C++, or Python.

Back to LeetCode Solutions