3. Longest Substring Without Repeating Characters

Posted on | Edited on | Views:

LeetCode

Approach 1: Brute Force, Time complexity : O(n^3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    private boolean allUnique(String s,int start,int end){
        Set<Character> set=new HashSet<>();
        for(int i=start;i<end;i++){
            if(set.contains(s.charAt(i))) return false;
            set.add(s.charAt(i));
        }
        return true;
    }
    public int lengthOfLongestSubstring(String s) {
        int n=s.length();
        int ans=0;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<=n;j++){
                if(allUnique(s,i,j)) ans=Math.max(j-i,ans);
            }
        }
        return ans;
    }
}

Approach 2: Sliding Window, Time complexity : O(2n) = O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n=s.length();
        Set<Character> set=new HashSet<>();
        int ans=0,i=0,j=0;
        while(i<=j&&j<n){
            // try to extend the range [i,j]
            if(!set.contains(s.charAt(j))) {
                set.add(s.charAt(j++));
                ans=Math.max(j-i,ans);
            }else{
                set.remove(s.charAt(i++));
            } 
        }
        return ans;
    }
}

Approach 3: Sliding Window Optimized, Time complexity : O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n=s.length();
        Map<Character,Integer> map=new HashMap<>();
        int ans=0,i=0,j=0;
        while(i<=j&&j<n){
            if(map.containsKey(s.charAt(j))) i=Math.max(map.get(s.charAt(j))+1,i);
            ans=Math.max(j-i+1,ans);
            map.put(s.charAt(j),j++);  
        }
        return ans;
    }
}

0%