Longest Substring Without Repeating Characters

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

example 1

Input: s = "abcabcbb" Output: 3

Explanation: The answer is "abc", with the length of 3. Note that "bca" and "cab" are also correct answers.

Brute Force Approach:

1. Initialize a variable maxLength to 0.

2. Use a nested loop to generate every possible substring. The outer loop, with index i, defines the start of the substring. The inner loop, with index j, defines the end.

3. For each substring, use a third loop or a hash set to check if it contains repeating characters.

4. Create an empty set to store characters for the current substring.

5. Iterate through the substring from i to j.

6. For each character, check if it is already in the set. If it is, the substring has duplicates, so you can stop checking this substring.

7. If the character is not in the set, add it.

8. If the substring is found to have all unique characters, calculate its length (j - i + 1) and update maxLength if the new length is greater.

9. After checking all possible substrings, the final maxLength will be the answer.

Time Complexity: O(N³) The outer two loops that generate all substrings contribute O(N²).The inner check for unique characters in each substring takes an additional O(N) time in the worst case, leading to a total time complexity of O(N³). This can be optimized to O(N²) if the uniqueness check is done more efficiently by using a set that is cleared for each new substring.

Space Complexity: O(M). The space complexity is determined by the storage needed to check for unique characters in each substring. In the worst-case scenario, the substring could be the entire string, so a hash set would require space proportional to the number of unique characters, M, which is at most N.

Optimal Approach:

Sliding window technique with HashSet

Steps:

1. Initialize two pointers start and end at the beginning of the string and a HashSet set to store unique characters.

2. Iterate over the String using end.

3. If the character at end is not in hashset, insert character in hashset, calculate the current window size end-start+1 and increment end.

4. if the character is present in the hashset, shrink window from the left until the duplicate character is removed.

5. continue till end reaches end of the string.

Java

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len=0,start=0,end=0,n=s.length();
        HashSet set = new HashSet<>();

        while(end<n){
         while(set.contains(s.charAt(end))&& start<end){

            set.remove(s.charAt(start));
            start++;
         }
         set.add(s.charAt(end));
         len=Math.max(len,end-start+1);
         end++;
        }
        return len;



    }
}

Time Complexity

The time complexity of the sliding window approach using a hash set is O(N), where n is the length of the string.

The end pointer iterates through the string from start to end, processing each character once.

The start pointer also moves through the string, but it only advances forward. In the worst case, it will traverse the length of the string once.

The hash set operations—add, remove, and contains—have an average-case time complexity of O(1).

Since both pointers traverse the string linearly and the hash set operations are constant time, the overall time complexity is linear, or O(N).

Space Complexity

The space complexity is O(k) or O(min(N,k)), where k is the size of the character set (or alphabet).

The hash set stores unique characters within the current sliding window.

In the worst-case scenario, all characters in the string are unique, and the size of the hash set will be equal to the length of the string (N).

However, the size of the hash set is also bounded by the size of the character set. For example, with standard ASCII characters, the set can hold at most 128 elements.

Therefore, the space required is the minimum of the string length and the size of the character set. For a fixed, small character set like ASCII, the space complexity can be considered O(1)(constant).