Longest Substring Without Repeating Characters

Java: Longest Substring Without Repeating Characters

Thought Process

To find the longest substring without repeating characters, we use a sliding window approach with a set to track unique characters. We maintain two pointers, start and end, to represent the current window. If the character at end is not in the set, it is added to the set, and the window expands. If the character is already in the set, the window shrinks from the start until the duplicate is removed. This ensures we always have a window of unique characters and track the maximum length.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        
        int start = 0;
        int end  = 0;
        int mxLength = 0;
        Set<Character> st = new HashSet<>();

        while(end<s.length()){

            if(!st.contains(s.charAt(end))){
                st.add(s.charAt(end));
                int length = end-start+1;
                mxLength = Math.max(mxLength,length);
                end++;
            }
            else{
                // Repeating character has been encountered
                st.remove(s.charAt(start));
                start++;
            }
        }
        return mxLength;
    }
}

Code Complexity

Time Complexity: O(n)

The algorithm iterates through the string once, making it linear in time complexity.

Space Complexity: O(min(m, n))

The algorithm uses a set to store unique characters, where 'm' is the size of the character set (e.g., ASCII) and 'n' is the length of the string.