LeetCode 3 - Longest Substring Without Repeating Characters


LeetCode – Longest Substring Without Repeating Characters (Java)
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.

https://discuss.leetcode.com/topic/68976/sliding-window-algorithm-template-to-solve-all-the-leetcode-substring-search-problem
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int begin = 0, end = 0, counter = 0, d = 0;

        while (end < s.length()) {
            // > 0 means repeating character
            //if(map[s.charAt(end++)]-- > 0) counter++;
            char c = s.charAt(end);
            map.put(c, map.getOrDefault(c, 0) + 1);
            if(map.get(c) > 1) counter++;
            end++;
            
            while (counter > 0) {
                //if (map[s.charAt(begin++)]-- > 1) counter--;
                char charTemp = s.charAt(begin);
                if (map.get(charTemp) > 1) counter--;
                map.put(charTemp, map.get(charTemp)-1);
                begin++;
            }
            d = Math.max(d, end - begin);
        }
        return d;
    }

X.
https://leetcode.com/articles/longest-substring-without-repeating-characters/
The above solution requires at most 2n steps. In fact, it could be optimized to require only n steps. Instead of using a set to tell if a character exists or not, we could define a mapping of the characters to its index. Then we can skip the characters immediately when we found a repeated character.
The reason is that if s[j] have a duplicate in the range [i, j) with index j&#x27;, we don't need to increase i little by little. We can skip all the elements in the range [i, j&#x27;] and let i to be j&#x27; + 1 directly.
https://discuss.leetcode.com/topic/8232/11-line-simple-java-solution-o-n-with-explanation
https://discuss.leetcode.com/topic/4083/shortest-o-n-dp-solution-with-explanations
the basic idea is, keep a hashmap which stores the characters in string as keys and their positions as values, and keep two pointers which define the max substring. move the right pointer to scan through the string , and meanwhile update the hashmap. If the character is already in the hashmap, then move the left pointer to the right of the same character last found. Note that the two pointers can only move forward.

I think there is no need to update longest evey time
The variable "j" is used to indicate the index of first character of this substring. If the repeated character's index is less than j itself, which means the repeated character in the hash map is no longer available this time

public int lengthOfLongestSubstring(String s) { if (s.length()==0) return 0; HashMap<Character, Integer> map = new HashMap<Character, Integer>(); int max=0; for (int i=0, j=0; i<s.length(); ++i){ if (map.containsKey(s.charAt(i))){ j = Math.max(j,map.get(s.charAt(i))+1); } map.put(s.charAt(i),i); max = Math.max(max,i-j+1); } return max; }
https://discuss.leetcode.com/topic/5781/my-accepted-o-n-java-solution
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        if (n == 0) return 0;
        
        int start = 0;
        int max = 0;
        Map<Character, Integer> lastSeens = new HashMap<Character, Integer>();
        for (int i = 0; i < n; i++) {
            Integer lastSeen = lastSeens.get(s.charAt(i));
            
            if (lastSeen != null)  {
                if (lastSeen >= start) {
                    max = Math.max(max, i - start);
                    start = lastSeen + 1;
                }
            }
            lastSeens.put(s.charAt(i), i);
        }
        max = Math.max(max, n - start);
        
        return max;
    }
https://discuss.leetcode.com/topic/27794/simple-java-solution
    public int lengthOfLongestSubstring(String s) {
        Map<Character,Integer> indices = new HashMap<Character,Integer>();
        int max = 0;
        int start = -1;
        int end = 0;
        for(end=0; end < s.length(); end++){
            char c = s.charAt(end);
            if(indices.containsKey(c)){
                int newstart = indices.get(c);
                start = Math.max(start,newstart);
            }
            max = Math.max(length,end-start);
            indices.put(c,end);
        }
        return max;
    }
X. Use int[256]
https://discuss.leetcode.com/topic/1914/my-o-n-solution/2
    public int lengthOfLongestSubstring(String s) {
        int[] occ = new int[256];
        
        int max = 0, counter = 0, start = 1;
        for (int i=0; i < s.length(); i++){
            char ch = s.charAt(i);
            if (occ[ch] >= start){
                counter -= occ[ch] - start + 1;
                start = occ[ch] + 1;
            }  
            occ[ch] = i+1;
            max = Math.max(max, ++counter);
        }
        
        return max;
    }
https://discuss.leetcode.com/topic/26483/o-n-time-o-1-space-solution-using-kadane-s-algo-in-java
Idea is that, while we traverse form left to right if we see a character at position j is a duplicate of a character at a position i < j on the left then we know that we can't start the substring from i anymore. So, we need to start a new substring from i+1 position. While doing this we also need to update the length of current substring and start of current substring. Important part of this process is to make sure that we always keep the latest position of the characters we have seen so far.
public int lengthOfLongestSubstring(String s) { int lastIndices[] = new int[256]; for(int i = 0; i<256; i++){ lastIndices[i] = -1; } int maxLen = 0; int curLen = 0; int start = 0; int bestStart = 0; for(int i = 0; i<s.length(); i++){ char cur = s.charAt(i); if(lastIndices[cur] < start){ lastIndices[cur] = i; curLen++; } else{ int lastIndex = lastIndices[cur]; start = lastIndex+1; curLen = i-start+1; lastIndices[cur] = i; } if(curLen > maxLen){ maxLen = curLen; bestStart = start; } } return maxLen; }

https://discuss.leetcode.com/topic/22048/my-easy-solution-in-java-o-n
    public int lengthOfLongestSubstring(String s) {
        int[] mOccur = new int[256];
        int maxL = 0;
        for(int i = 0, j = 0; i < s.length(); ++i){
            char ch = s.charAt(i);
            ++mOccur[ch];
            while(mOccur[ch] > 1){
                --mOccur[s.charAt(j++)];
            }
            maxL = Math.max(maxL, i - j + 1);
        }
        return maxL;
    }
http://n00tc0d3r.blogspot.com/2013/04/longest-substring-without-repeating.html
 public int lengthOfLongestSubstring(String s) {  
   int maxLen = 0;  
   int start = 0, end = 0;  
   // a map mapping a char to its prior index in s  
   HashMap<Character, Integer> map = new HashMap<Character, Integer>();  
   while (end < s.length()) {  
     char cur = s.charAt(end);  
     if (map.containsKey(cur) && map.get(cur) >= start) {  
       // hit a recurrence  
       maxLen = Math.max(maxLen, end-start);  
       start = map.get(cur) + 1;  
     }  
     map.put(cur, end++);  
   }  
   maxLen = Math.max(maxLen, end-start);  
   return maxLen;  
 }
http://ajeetsingh.org/2013/11/10/given-a-string-find-maximum-size-of-a-sub-string-in-which-no-duplicate-character-present/
We can also use int[256] to store the index.
public static int find(String source){
    int window = 0;
    int start = 0;
    int i =0;
    HashMap<Character, Integer> map = new HashMap<Character, Integer>();
    while( i < source.length()){
        if(map.containsKey(source.charAt(i))){ 
            int currentWindow = i-start;
            if(window < currentWindow){
                window = currentWindow;
            }
            start = map.get(source.charAt(i)) + 1;
            //no need map.clear();
        }
        if(i+1 == source.length()){
            int currentWindow = i-start +1;
            if(window < currentWindow){
                window = currentWindow;
            }
            return window;
        }
        map.put(source.charAt(i), i);
        i++;
    }  
    return 0;
}

http://www.zrzahid.com/longest-sub-string-with-no-duplicate-chars/
    public static int lengthOfLongestNonrepeatedSubstring(String s) {
        int lastIndices[] = new int[256];
        for(int i = 0; i<256; i++){
            lastIndices[i] = -1;
        }
        
        int maxLen = 0;
        int curLen = 0;
        int start = 0;
        int bestStart = 0;
        for(int i = 0; i<s.length(); i++){
            char cur = s.charAt(i);
            if(lastIndices[cur]  < start){
                lastIndices[cur] = i;
                curLen++;
            }
            else{
                int lastIndex = lastIndices[cur];
                start = lastIndex+1;
                curLen = i-start+1;
                lastIndices[cur] = i;
            }
            
            if(curLen > maxLen){
                maxLen = curLen;
                bestStart = start;
            }
        }
        
        return maxLen;
    }

X. Using HashSet
https://leetcode.com/discuss/60645/share-my-java-solution-using-hashset
  • Time complexity : O(2n) = O(n). In the worst case each character will be visited twice by i and j.
  • Space complexity : O(min(m, n)). Same as the previous approach. We need O(k) space for the sliding window, where k is the size of the Set. The size of the Set is upper bounded by the size of the string n and the size of the charset/alphabet m. 
The idea is use a hash set to track the longest substring without repeating characters so far, use a fast pointer j to see if character j is in the hash set or not, if not, great, add it to the hash set, move j forward and update the max length, otherwise, delete from the head by using a slow pointer i until we can put character j to the hash set.
public int lengthOfLongestSubstring(String s) { int i = 0, j = 0, max = 0; Set<Character> set = new HashSet<>(); while (j < s.length()) { if (!set.contains(s.charAt(j))) { set.add(s.charAt(j++)); max = Math.max(max, set.size()); } else { /// this runs multiple times set.remove(s.charAt(i++)); } } return max; }
if we use hashmap to store the position of occured characters. Then we don't need to find the next start position by set.remove(s.charAt(i++)); .
We just put i = map[s[j]] + 1

http://www.lifeincode.net/programming/leetcode-longest-substring-without-repeating-characters/
http://comproguide.blogspot.com/2014/09/longest-substring-with-unique-characters.html
http://www.programcreek.com/2013/02/leetcode-longest-substring-without-repeating-characters-java/
    public int lengthOfLongestSubstring(String s) {
        if (s.length() <= 1)
            return s.length();
        int prev = 0;
        boolean[] letter = new boolean[256];
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            if (!letter[s.charAt(i)])
                letter[s.charAt(i)] = true;
            else {
                while (s.charAt(prev) != s.charAt(i)) {
                    letter[s.charAt(prev)] = false;
                    prev++;
                }
                prev++;
            }
            max = Math.max(max, i - prev + 1);
        }
        return max;
    }
http://www.geeksforgeeks.org/length-of-the-longest-substring-without-repeating-characters/
This solution uses extra space to store the last indexes of already visited characters. The idea is to scan the string from left to right, keep track of the maximum length Non-Repeating Character Substring (NRCS) seen so far. Let the maximum length be max_len. When we traverse the string, we also keep track of length of the current NRCS using cur_len variable. For every new character, we look for it in already processed part of the string (A temp array called visited[] is used for this purpose). If it is not present, then we increase the cur_len by 1. If present, then there are two cases:
a) The previous instance of character is not part of current NRCS (The NRCS which is under process). In this case, we need to simply increase cur_len by 1.
b) If the previous instance is part of the current NRCS, then our current NRCS changes. It becomes the substring staring from the next character of previous instance to currently scanned character. We also need to compare cur_len and max_len, before changing current NRCS (or changing cur_len).
int longestUniqueSubsttr(char *str)
{
    int n = strlen(str);
    int cur_len = 1;  // To store the lenght of current substring
    int max_len = 1;  // To store the result
    int prev_index;  // To store the previous index
    int i;
    int *visited = (int *)malloc(sizeof(int)*NO_OF_CHARS);
    /* Initialize the visited array as -1, -1 is used to indicate that
       character has not been visited yet. */
    for (i = 0; i < NO_OF_CHARS;  i++)
        visited[i] = -1;
    /* Mark first character as visited by storing the index of first
       character in visited array. */
    visited[str[0]] = 0;
    /* Start from the second character. First character is already processed
       (cur_len and max_len are initialized as 1, and visited[str[0]] is set */
    for (i = 1; i < n; i++)
    {
        prev_index =  visited[str[i]];
        /* If the currentt character is not present in the already processed
           substring or it is not part of the current NRCS, then do cur_len++ */
        if (prev_index == -1 || i - cur_len > prev_index)
            cur_len++;
        /* If the current character is present in currently considered NRCS,
           then update NRCS to start from the next character of previous instance. */
        else
        {
            /* Also, when we are changing the NRCS, we should also check whether
              length of the previous NRCS was greater than max_len or not.*/
            if (cur_len > max_len)
                max_len = cur_len;
            cur_len = i - prev_index;
        }
        visited[str[i]] = i; // update the index of current character
    }
    // Compare the length of last NRCS with max_len and update max_len if needed
    if (cur_len > max_len)
        max_len = cur_len;
    free(visited); // free memory allocated for visited
    return max_len;
}
How can we can look up if a character had existed in the substring instantaneously? The answer is using a simple table to store the characters that have appeared.
http://leetcode.com/2011/05/longest-substring-without-repeating-characters.html
int lengthOfLongestSubstring(string s) {
  int n = s.length();
  int i = 0, j = 0;
  int maxLen = 0;
  bool exist[256] = { false };
  while (j < n) {
    if (exist[s[j]]) {
      maxLen = max(maxLen, j-i);
      while (s[i] != s[j]) {
        exist[s[i]] = false;
        i++;
      }
      i++;
      j++;
    } else {
      exist[s[j]] = true;
      j++;
    }
  }
  maxLen = max(maxLen, n-i);
  return maxLen;
}
public static int lengthOfLongestSubstring3(String s) { int max = 0; HashSet<Character> set = new HashSet<Character>(); int candidateStartIndex = 0; for (int iter = 0; iter < s.length(); ++iter) { char c = s.charAt(iter); if (set.contains(c)) { max = Math.max(max, iter - candidateStartIndex); while (s.charAt(candidateStartIndex) != s.charAt(iter)) { set.remove(s.charAt(candidateStartIndex)); candidateStartIndex++; } candidateStartIndex++; } else { set.add(c); } } max = Math.max(max, s.length() - candidateStartIndex); return max; }

X. Brute Force - O(1) space
The idea is pretty simple. We iterate thru the list once and we keep a pointer of where the current longest possible substring starts. During the iteration, we check if this last character is contained in the current substring. If so, move the ptr to the first index of the char at the string +1. Everytime we will compare and keep the max value up to date.
    public int lengthOfLongestSubstring(String s) {
        if (s.length() <= 1) return s.length();
        
        int max = 1;
        int ptr = 0;
        for (int i = 1; i< s.length(); i++) {
            // find the first occurence of the char after index ptr
            int index = s.indexOf(s.charAt(i), ptr); 
            if (index < i) { // it means that it is contained in s.substring(ptr, i)
                ptr = index + 1;
            }
            max = Math.max(max, i - ptr + 1);
        }
        
        return max;
    }

 LeetCode – Longest Substring Without Repeating Characters (Java) O(n^3)
public static int lengthOfLongestSubstring(String s) {
 
 char[] arr = s.toCharArray();
 int pre = 0;
 
 HashMap<Character, Integer> map = new HashMap<Character, Integer>();
 
 for (int i = 0; i < arr.length; i++) {
  if (!map.containsKey(arr[i])) {
   map.put(arr[i], i);
  } else {
   pre = pre > map.size() ? pre : map.size();
   i = map.get(arr[i]);
   map.clear();
  }
 }
 
 return Math.max(pre, map.size());
}
https://medium.com/@xingren14/3-longest-substring-without-repeating-characters-5e01bc265098
不是一道难题但是有两个值得注意的坑
  1. 如果用map统计并不重复的char的话，然后选择遇到重复字符就clear map再重置index的话，会超时，因为有大量重复操作
  2. 添加辅助的start指针，长度用i和start之间的差来计算。 这样做就不会超时了。要注意的是start 的重置logic，每当遇到重复字符的时候，start不一定是要设成当前重复字符的原index的下一个，而是要看当前的start和这个index+1谁更大，因为有可能index+1会小于当前的start这样会造成错误。
  3. 最后记得收尾，比较s.length-start的长度是否更长
Read full article from LeetCode – Longest Substring Without Repeating Characters (Java)
at
Labels: , , , , , , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts