Burak Dede's Blog

Longest Substring Without Repeating Character Problem - Leetcode

Problem

This is my approach to the solution of add two numbers problem from Leetcode. https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

Solution #1

My first approach is using something like HasMap and keep index of each element appeared. Using sliding window approach (window is the size of the unique substring) if we found duplicate we update window left index until previous occurance of the duplicate element in one operation. For each addition we also update max which keep longest substring we found until that time.

public static int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> map = new HashMap<>();
    int max = 0;
    for(int i = 0, j = 0; j < s.length(); j++) {
        if (map.containsKey(s.charAt(j))) {
            i = Math.max(i, map.get(s.charAt(j)));
        }
        max = Math.max(max, j - i + 1);
        map.put(s.charAt(j), j + 1);
    }

    return max;
}

This would take O(n) time complexity and depending on the longest substring O(min(substring length, total string size)) space complexity. This passses all test cases but I think leetcode solution is better using HashMap with sliding window approach.

We can use HashSet but since we do not know the duplicate element we are removing it will take more computation but still O(n) time.