Wednesday, June 24, 2020

Leetcode discuss: 3. Longest Substring Without Repeating Characters

Here is the post. 

C# slide window optimal time algorithm practice in June 2020

June 24, 2020
It took me less than 15 minutes to solve the algorithm. I came out slide window idea, and also wrote the code and tested the code using three test cases, "a","aa" and "baa".

Here are highlights:

  1. Slide window technique is to keep two pointers, right side called index variable, left side called left variable;
  2. Keep a hashset of found chars, if the duplicate is found, then skip left side char until a duplicate one found;
  3. Most of important is to go over the code line by line using three test cases: "a","aa" and "baa"
  4. Stay clam and test the code line by line. This practice I caught myself missing "index++" when I tested the case "aa".
public class Solution {
    public int LengthOfLongestSubstring(string s) {
        if(s == null || s.Length == 0)
            return 0; 
        
        // slide window - unique
        int max = 0; 
        var set = new HashSet<char>(); 
        int left = 0; 
        int index = 0; 
        var length = s.Length; 
        
        // "a"
        // "aa"
        // "baa"
        while(index < length)
        {
            //work on sliding window
            var current = s[index]; // 'a'
            
            // skip size of window is 1
            while(set.Contains(current) && left < index) // true
                  {
                      var leftChar = s[left]; // 'a'
                      if(leftChar == s[index])
                      {                         
                          set.Remove(leftChar); // {}
                          left++; // 2
                          break;
                      }
                      
                      set.Remove(leftChar); // {'a'}
                      left++; // 1
                  }
                  
            //
                  set.Add(s[index]); // {'a'}
                  var size = index - left + 1; // 1
                  max = size > max? size : max; // 2
                
                  index++; // 2
        }
                  
                  return max; 
    }
}

No comments:

Post a Comment