Longest Substring Without Repeating Characters

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

The problem asks us to find the length of the longest substring that contains only unique characters.

Problem Statement

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

Example

Input: s = "abcabcbb"

Output: 3

Explanation:

"abc"

is the longest substring without repeating characters.

---

Brute Force Approach

Generate all possible substrings and check whether every character inside the substring is unique.

Interview Explanation

For each starting index, keep extending the substring and use a HashSet to detect duplicates. If a duplicate character appears, stop extending that substring. Track the maximum valid length found.

Complexity Analysis

• Time Complexity: O(N²)
• Space Complexity: O(N)

Brute Force Code

class Solution {
    public int lengthOfLongestSubstring(String s) {

        int maxLen = 0;

        for (int i = 0; i < s.length(); i++) {

            HashSet<Character> set = new HashSet<>();

            for (int j = i; j < s.length(); j++) {

                if (set.contains(s.charAt(j))) {
                    break;
                }

                set.add(s.charAt(j));
                maxLen = Math.max(maxLen, j - i + 1);
            }
        }

        return maxLen;
    }
}

---

Optimal Approach: Sliding Window + HashMap

Intuition

As long as all characters inside the current window are unique, we can continue expanding the window.

If a duplicate character appears, the window becomes invalid. Instead of rebuilding the substring, we move the left pointer forward until the duplicate is removed.

The sliding window always represents a valid substring with unique characters.

Why HashMap?

The HashMap stores:

Character -> Frequency

Whenever a frequency becomes greater than 1, we know a duplicate character exists inside the current window.

---

Dry Run

s = "abcabcbb"

Left	Right	Window	Valid	Max Length
0	0	a	Yes	1
0	1	ab	Yes	2
0	2	abc	Yes	3
0	3	abca	No	3
1	3	bca	Yes	3
1	4	bcab	No	3
2	4	cab	Yes	3

The longest valid substring found is:

"abc"

Length:

3

---

Optimal Java Solution

class Solution {
    public int lengthOfLongestSubstring(String s) {

        HashMap<Character, Integer> map = new HashMap<>();

        int left = 0;
        int maxLen = 0;

        char[] chars = s.toCharArray();

        for (int right = 0; right < chars.length; right++) {

            map.put(chars[right],
                    map.getOrDefault(chars[right], 0) + 1);

            while (map.get(chars[right]) > 1) {

                map.put(chars[left],
                        map.get(chars[left]) - 1);

                if (map.get(chars[left]) == 0) {
                    map.remove(chars[left]);
                }

                left++;
            }

            maxLen = Math.max(maxLen, right - left + 1);
        }

        return maxLen;
    }
}

---

Complexity Analysis

• Time Complexity: O(N)
• Space Complexity: O(K)

Where K is the number of distinct characters present in the string.

---

Key Takeaway

Whenever a problem asks for:

Longest substring with all unique characters

Think:

Sliding Window + HashMap

Expand the window while it remains valid. When a duplicate character appears, shrink the window until the duplicate is removed. This pattern appears frequently in string and array interview questions.

Connect With Me

• GitHub: https://github.com/codewithjaspreet
• LinkedIn: https://www.linkedin.com/in/jaspreetsodhi482/
• Instagram: https://instagram.com/jaspreet.dev

If you found this helpful, consider following for more Data Structures & Algorithms, System Design, and Software Engineering content.