Longest Substring Without Repeating Characters

• Click here to see the full article post

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

• @ZhangRuisen Thanks! Fixed.

• This post is deleted!

• "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)

• @wenlong9 Thanks, fixed!

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

• @yashao @giridharan Thanks, fixed.

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

• Thanks for the solution!

• 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)

• 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;

}
``````

• 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??

• 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;
}
``````

• 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;
}
``````

}

• 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;

}
};``````

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

• 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);
}``````

• This post is deleted!

• This post is deleted!

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