Longest Substring Without Repeating Characters

problem link : Longest Substring Without Repeating Characters

Brute Force Solution O(n^3) time complexity

JAVA
1public int lengthOfLongestSubstring(String s) {
2    int len = 0;
3    // Iterate through all possible substrings starting at index i
4    for (int i = 0; i < s.length(); i++) {
5        for (int j = i; j < s.length(); j++) {
6            // Get substring from index i to j
7            String sub = s.substring(i, j + 1);
8            // Use a set to check for duplicate characters
9            HashSet<Character> set = new HashSet<>();
10            int f = 0;
11            // Check if the substring has all unique characters
12            for (int k = 0; k < sub.length(); k++) {
13                if (set.contains(sub.charAt(k))) {
14                    f = 1; // Duplicate found
15                    break;
16                }
17                set.add(sub.charAt(k));
18            }
19            // If all characters are unique, update the max length
20            if (f == 0) {
21                len = Math.max(len, sub.length());
22            }
23        }
24    }
25    return len;
26}

Optimal Solution O(n) time complexity

JAVA
1public int lengthOfLongestSubstring(String s) {
2    int len = 0, tptr = 0; // tptr: left boundary of the sliding window
3    HashSet<Character> set = new HashSet<>();
4    // i is the right boundary of the sliding window
5    for (int i = 0; i < s.length(); i++) {
6        char ch = s.charAt(i);
7        // Shrink the window from the left until there are no duplicates
8        while (set.contains(ch)) {
9            set.remove(s.charAt(tptr++));
10        }
11        set.add(ch); // Add current character to the set
12        len = Math.max(len, set.size()); // Update max length
13    }
14    return len;
15}