20-Longest-Substring-Without-Repeating.md

Longest Substring Without Repeating Characters

Problem Link

https://leetcode.com/problems/longest-substring-without-repeating-characters/

---

Pattern

• Sliding Window
• Hash Table

---

Approach

Expand window, track char positions; when duplicate found, shrink from left until duplicate removed.

---

Time Complexity

O(n)

Space Complexity

O(n)

---

Java Solution

import java.util.*;
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int left = 0, ans = 0;
        for (int right = 0; right < s.length(); right++) {
            if (map.containsKey(s.charAt(right))) {
                left = Math.max(left, map.get(s.charAt(right)) + 1);
            }
            map.put(s.charAt(right), right);
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}