Leetcode discuss: 3. Longest Substring Without Repeating Characters

Here is the link. 

C# warmup practice in June 25 2020

June 25, 2020

Introduction

The problem is to find longest unique substring. It is a classical algorithm for sliding window technique. I wrote one using two nested loops, so I like to write second one using one loop only.

I also like to write a solution based on simple structure of code, only use one loop - while loop. How to write quality code involving good design - avoid index-out-of-range error, simple structure of code as well.

Case study
"aab"
Sliding window can be marked using two variables, one is left, one is index; both start from 0. Each char will be checked if it is duplicated or not. If it is, then the char will be removed from hash set found, and also left pointer increments one. Otherwise, the char will be added to found hashset, and then update max - size of sliding window containing unique characters, move to next iteration.

I practice a solution using two loops. Here is the link. So I like to write a solution to use only one loop instead.

Time complexity
O(N), N is the length of string.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _3_longest_substring___review
{
    class Program
    {
        static void Main(string[] args)
        {
        }

        /// <summary>
        /// code review on June 25, 2020
        /// "a"
        /// "aa"
        /// "abc"
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public int LengthOfLongestSubstring(string s)
        {            
            if (s == null || s.Length == 0)
            {
                return 0;
            }

            int length = s.Length;

            var found = new HashSet<int>();

            int max = 0;                     

            int left = 0;
            int index = 0; 

            while(index < length && left <= index)  // caught by debugger - add left <= index
            {
                var current = s[index];   
                var duplicate = found.Contains(current);  
                var leftChar = s[left];  

                // duplicate char to remove
                if (duplicate)
                {
                    found.Remove(leftChar);  
                    left++;                   
                    continue; 
                }

                found.Add(current);                                  
                
                max = Math.Max(max, index - left + 1);  
                index++;                                                    
            }

            return max;
        }       
    }
}