Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save yitonghe00/45621eca226617c215db795161f2d0e5 to your computer and use it in GitHub Desktop.
Save yitonghe00/45621eca226617c215db795161f2d0e5 to your computer and use it in GitHub Desktop.
3. Longest Substring Without Repeating Characters
// Two pointer solution: min/max substring templete
// Time: O(n), 2ms
// Space: O(1), 37.4mb
class Solution {
public int lengthOfLongestSubstring(String s) {
// char table that keeps track of characters we have met
int[] table = new int[128];
int count = 0; // Count of unique char
int begin = 0, end = 0, maxLen = 0; // Window is [begin, end)
while(end < s.length()) {
// Expand window to the right
if(table[s.charAt(end++)]++ == 0) {
// table[] was 0 before, this is the first char in the table
count++;
}
// Shrink the window from left side until we don't have repeating char
while(end - begin > count) {
// Shrink the window
if(table[s.charAt(begin++)]-- == 1) {
// If we delete the last char in the window
count--;
}
}
// Update length when we don't have repeating char
if(end - begin > maxLen) {
maxLen = end - begin;
}
}
return maxLen;
}
}
class Solution {
public int lengthOfLongestSubstring(String s) {
int[] table = new int[128];
for(int i = 0; i < table.length; i++) table[i] = -1;
int begin = 0, end = 0, ans = 0;
while(end < s.length()) {
//Move the end pointer to make it invalid
while(end < s.length() && table[s.charAt(end)] == -1) {
table[s.charAt(end++)] = end;
ans = Math.max(ans, end - begin);
//Note: We need to update the ans more often if we move end more than 1 step in the outer while loop
}
//Move the begin pointer directly to make it valid
if(end < s.length()) {
if(table[s.charAt(end)] != -1) {
while(begin < table[s.charAt(end)] + 1)
table[s.charAt(begin++)] = -1;
}
table[s.charAt(end++)] = end;
}
//Now [begin, end) is a valid solution
ans = Math.max(ans, end - begin);
}
return ans;
}
}
//Solution #1: Two pointers (Sliding window)
//Difference between two pointers and iteratoin: Just remove the first one when meet duplicates, instead of remove all.
class Solution {//abcad
public int lengthOfLongestSubstring(String s) {
int i = 0, j = 0, n = s.length(), ans = 0;
Set<Character> set = new HashSet<>();
while(i < n && j < n) {
if(!set.add(s.charAt(j))) {
set.remove(s.charAt(i++));
} else {
ans = Math.max(ans, j - i + 1);
j++;
}
}
return ans;
}
}
//Solution #2: Revised Two pointers
//Move more steps when meet duplicates: use a hash table to save the index
class Solution {
public int lengthOfLongestSubstring(String s) {
int i = 0, j = 0, n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>(); //Save the index in the map
for(i = 0, j = 0; j < n; j++) {
if(map.containsKey(s.charAt(j))) {
i = Math.max(i, map.get(s.charAt(j)) + 1); //Move i untill there is no overlap
}
map.put(s.charAt(j), j);
ans = Math.max(ans, j - i + 1); //tmmzuxt
}
return ans;
}
}
//Solution #3: Revised Two pointers
//Move more steps when meet duplicates: use a table to save the index when character range is fixed
class Solution {
public int lengthOfLongestSubstring(String s) {
int i = 0, j = 0, n = s.length(), ans = 0;
int[] table = new int[256]; //Save the index in the table (range is fixed) (default value: 0)
for(i = 0, j = 0; j < n; j++) {
i = Math.max(i, table[s.charAt(j)]); //Move i untill there is no overlap
table[s.charAt(j)] = j + 1;
ans = Math.max(ans, j - i + 1); //tmmzuxt
}
return ans;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment