Longest Substring Without Repeating Characters

Description

Longest Substring Without Repeating Characters
Given a string s, find the length of the longest substring without repeating characters.

Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, “pwke” is a subsequence and not a substring.

Constraints:

• 0 <= s.length <= 5 * 10^4
• s consists of English letters, digits, symbols and spaces.

Approach

• Time: O(n) Space: O(n)

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> data = new HashSet<>();
        int longest = 0;
        int start = 0;
 
        for (int end = 0; end < s.length(); end++) {
            while (data.contains(s.charAt(end))) {
                data.remove(s.charAt(start));
                start++;
            }
            data.add(s.charAt(end));
            longest = Math.max(longest, end - start + 1);
        }
 
        return longest;
    }
}

Brute Force Approach (Nested Loops)

Intuition:
Check every possible substring in the string. Expand the substring character by character from each starting index, stopping as soon as a duplicate character is seen.

Algorithm:

1. Outer loop (i) sets the starting character of the substring.
2. Inner loop (j) expands the end of the substring.
3. A boolean array tracks characters seen in the current substring window.
4. If a duplicate is encountered, stop the inner loop and move to the next starting position i.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int maxLength = 0;
        int n = s.length();
 
        for (int i = 0; i < n; i++) {
            boolean[] visited = new boolean[256]; // Tracks characters seen in current window
            
            for (int j = i; j < n; j++) {
                char ch = s.charAt(j);
                
                // Stop expanding if character is a duplicate
                if (visited[ch]) {
                    break;
                }
                
                visited[ch] = true;
                maxLength = Math.max(maxLength, j - i + 1);
            }
        }
        return maxLength;
    }
}
 

• Time Complexity: $O(N^2)$ — Checks up to $N^2$ substrings in the worst case.
• Space Complexity: $O(1)$ — Fixed auxiliary space of 256 boolean flags.

---

Optimal & Intuitive Approach (Sliding Window + HashSet)

Intuition:
Maintain a dynamic window between two pointers (start and end). As end moves right to expand the window, check if the incoming character exists in the HashSet. If it does, incrementally shrink the window from start by removing characters until the duplicate is eliminated.

Algorithm:

1. Advance the end pointer across the string to expand the window.
2. While s[end] is already in the HashSet, remove s[start] from the set and increment start.
3. Add s[end] to the set.
4. Recalculate longest = Math.max(longest, end - start + 1).

import java.util.HashSet;
import java.util.Set;
 
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> data = new HashSet<>();
        int longest = 0;
        int start = 0;
 
        for (int end = 0; end < s.length(); end++) {
            // Shrink window from the left until duplicate is removed
            while (data.contains(s.charAt(end))) {
                data.remove(s.charAt(start));
                start++;
            }
            
            // Add current character and track max size
            data.add(s.charAt(end));
            longest = Math.max(longest, end - start + 1);
        }
 
        return longest;
    }
}
 

• Time Complexity: $O(N)$ — Each character is added to and removed from the set at most once ($2N$ operations max).
• Space Complexity: $O(\min (N,M))$ — Where $M$ is the size of the character set.