Longest Substring Without Repeating Characters




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(ji > max) max = ji; // 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==k1)c++; } j++; } //printf("%d %d ",i,j); if(c==0&&ji>max) max=ji; return max; }

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

My Java Solution, used HashMap
Space Complexity O(distinct chars in string)
Time Complexity O(n) where n is number of chars in stringpublic 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, istartPointer); startPointer = map.get(c)+1; } map.put(c,i); } return Math.max(maxLength, s.length()startPointer); }