Longest Substring Without Repeating Characters


  • 0

    Click here to see the full article post


  • 0
    Z

    Approach #1 Brute Force (Java)
    The code [Character ch = s.charAt(start); ] should be [Character ch = s.charAt(i); ].
    Not "start", should be "i".


  • 0

    @ZhangRuisen Thanks! Fixed.


  • 0
    C
    This post is deleted!

  • 0
    W

    "Then we have 0<i<j≤n (here end index j is exclusive by convention)"
    should be
    "Then we have 0<=i<j≤n ..."
    The i is in range [0,n)


  • 0

    @wenlong9 Thanks, fixed!


  • 0
    S

    @giridharan yeah, it's the same, i figured it out for a while, made me confused too, lol~


  • 0

    @yashao @giridharan Thanks, fixed.


  • 0
    S

    the solution is very good, step by step to improve the performance of the code, and the explanation is very clear. Thanks~


  • 0
    T

    Thanks for the solution!


  • 0
    F

    Hi, the time complexity for the brute force should be wrong, the allUnique use Set, which has O(n^2) complexity for insert operation. Thus, you have 2 for loop * n^2; should be O(n^4)


  • 0
    M

    Here is my solution in C that runs in O(length_of_string) time.

    int lengthOfLongestSubstring(char* s) {
        int h[200]={0},i=0,j=0,k=strlen(s),t[200],pre[200],max=k==0?0:1,c=0;
        for(;i<200;i++)
        t[i]=1;
        i=0;
        while(j < k){
             h[s[j]]++;
            if(h[s[j]]==1){
                pre[s[j]]=j;
            }
            else{
                if(j-i > max)
                max = j-i;
               // t[s[j]] = h[s[j]];
               int x;
               for(x=i;x<=pre[s[j]];x++)
               h[s[x]]--;
                i=pre[s[j]] + 1;
                pre[s[j]] = j;
                if(j==k-1)c++;
            }
            j++;
        }
        //printf("%d %d ",i,j);
        if(c==0&&j-i>max)
        max=j-i;
        return max;
        
    }
    

  • 0
    _

    Is it possible to know the best answer that has been posted?
    My solution takes 16ms for all the test cases, which happens to be ~64% faster than other solutions.
    What was the method used for the top performing solution??


  • 0
    W

    C version of "Sliding Window Optimized"

    #define    LEN          (256)
    #define    MAX(a, b)    ((a) > (b)) ? (a) : (b)
    
    int lengthOfLongestSubstring(char* s) {
        int index[LEN] = {0};
        int max = 0;
        int i, j;
        
        for (i = 0, j = 0; s[j]; j++)
        {
            i = MAX(index[s[j]], i);
            max = MAX((j - i + 1), max);
            index[s[j]] = j + 1;
        }
        
        return max;
    }
    

  • -1
    J

    simple JAVA solution:

    public class Solution {
    public boolean canJump(int[] nums) {
    if (nums == null) return false;

        int maxVal = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            int targetVal = Math.max(maxVal, i + nums[i]);
            if (targetVal <= i) return false;
            maxVal = targetVal;
        }
    
        return true;
    }
    

    }


  • 0
    A

    C++ implementation

    #include "stdafx.h"
    #include <map>
    #include <string>
    using namespace std;
    class Solution {
    public:
    	Solution();
    	~Solution();
        int lengthOfLongestSubstring(string s) {
            int ans = 0, left = 0, len = s.length();
            int last[255];
            memset(last, -1, sizeof last);
            
            for (int i = 0; i < len; i++) {
               
                if (last[s[i]] >= left){ 
    				left = last[s[i]] + 1;
    			}
    			last[s[i]] = i;
                ans = max(ans, i - left + 1);
            }
            return ans;
        
        }
    };

  • 0
    C

    Test Case show That confused me:
    Given "dvdf"
    expected 3 .
    But how....substring without repeating characters


  • 0
    M

    My Java Solution, used HashMap
    Space Complexity O(distinct chars in string)
    Time Complexity O(n) where n is number of chars in string

    public int lengthOfLongestSubstring(String s) {
        
        int startPointer = 0, maxLength = Integer.MIN_VALUE;
        HashMap<Character,Integer> map = new HashMap<Character,Integer>();
        
        for(int i = 0; i < s.length(); i++)
        {
            char c = s.charAt(i);
            
            if(map.containsKey(c)&&map.get(c)>=startPointer)
             {   
                 maxLength = Math.max(maxLength, i-startPointer);
                 startPointer = map.get(c)+1;
             }
            map.put(c,i);
        }
        return Math.max(maxLength, s.length()-startPointer);
    }

  • -1
    A
    This post is deleted!

  • 0
    A
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.