Created
December 1, 2014 10:58
-
-
Save wangchauyan/fdf0e5cfa06ab7e2c659 to your computer and use it in GitHub Desktop.
Longest sub string in a string - LeetCode
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
Given a string, find the length of the longest substring without repeating characters. | |
For example, the longest substring without repeating letters for "abcabcbb" is "abc", | |
which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1. | |
*/ | |
public class Solution { | |
public int lengthOfLongestSubstring(String s) { | |
if(s == null || s.length() == 0) return 0; | |
// Time Complexity = O(n*2) = O(n), Space Complexity = O(n) | |
int max = 0; | |
int slow = 0; | |
int fast = 0; | |
HashSet<Character> set = new HashSet<Character>(); | |
while(fast < s.length()) { | |
if(set.contains(s.charAt(fast))) { | |
max = Math.max(max, fast - slow); | |
while(s.charAt(slow) != s.charAt(fast)) { | |
set.remove(s.charAt(slow)); | |
slow++; | |
} | |
slow++; | |
} else set.add(s.charAt(fast)); | |
fast++; | |
} | |
max = Math.max(max, fast - slow); | |
return max; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment