Longest Substring Without Repeating Characters

🧩 Problem Statement

Given a string s, find the length of the longest substring without repeating characters.

---

✍️ Function Signature

public int lengthOfLongestSubstring(String s)

---

🚀 Approaches

✅ 1. Sliding Window with HashSet (Two Pointers)

public int lengthOfLongestSubstring(String s) {
    Set<Character> set = new HashSet<>();
    int left = 0, maxLen = 0;
    for (int right = 0; right < s.length(); right++) {
        while (set.contains(s.charAt(right))) {
            set.remove(s.charAt(left++));
        }
        set.add(s.charAt(right));
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

• Time Complexity: O(n)
• Space Complexity: O(k) (k = number of unique characters)
• 🚀 Efficient and widely accepted approach

---

🧠 2. Sliding Window with HashMap (Optimized Jumping)

public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> map = new HashMap<>();
    int maxLen = 0;
    for (int right = 0, left = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (map.containsKey(c)) {
            left = Math.max(map.get(c) + 1, left);
        }
        map.put(c, right);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

• Time Complexity: O(n)
• Space Complexity: O(k)
• ⚡ Optimized over Set-based window; avoids multiple character deletions

---

🔄 3. Brute Force (For Understanding Only)

public int lengthOfLongestSubstring(String s) {
    int maxLen = 0;
    for (int i = 0; i < s.length(); i++) {
        Set<Character> set = new HashSet<>();
        int j = i;
        while (j < s.length() && !set.contains(s.charAt(j))) {
            set.add(s.charAt(j++));
        }
        maxLen = Math.max(maxLen, j - i);
    }
    return maxLen;
}

• Time Complexity: O(n²)
• Space Complexity: O(k)
• 🚫 Not optimal for large inputs

---

🧪 Test Cases

public class LongestSubstringTest {
    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("abcabcbb")); // 3
        System.out.println(lengthOfLongestSubstring("bbbbb"));    // 1
        System.out.println(lengthOfLongestSubstring("pwwkew"));   // 3
        System.out.println(lengthOfLongestSubstring(""));         // 0
        System.out.println(lengthOfLongestSubstring("dvdf"));     // 3
    }

    public static int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int left = 0, maxLen = 0;
        for (int right = 0; right < s.length(); right++) {
            while (set.contains(s.charAt(right))) {
                set.remove(s.charAt(left++));
            }
            set.add(s.charAt(right));
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}

---

📝 Notes

• Use HashMap-based method for interviews — avoids unnecessary operations
• Sliding window is efficient for large input strings
• Consider edge cases: empty string, all repeating characters, all unique characters