Leetcode Problem 3 Longest Substring Without Repeating Characters.txt

3. Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 
Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.



Hint to solving: Just take the two pointer approach and extra space of dictionary to get the solution in linear time.

public class Solution 
{
    public int LengthOfLongestSubstring(string s) 
    {
        if(s.Length == 0)
            return 0;
        int globalMax = 0;
        int startIndex = 0;
        
        Dictionary<char, int> uniqueCharacters = new Dictionary<char,int>();
        
        for(int i = 0; i<s.Length; ++i)
        {
            if(uniqueCharacters.ContainsKey(s[i]) == false)
            {
                uniqueCharacters.Add(s[i],i);
            }
            else
            {
                if(uniqueCharacters[s[i]] >= startIndex)
                {
                    startIndex = uniqueCharacters[s[i]] + 1;
                }
                uniqueCharacters[s[i]] = i;
            }
            
            if(i-startIndex > globalMax)
            {
                globalMax = i-startIndex;
            }
        }
            
        return globalMax+1;
    }
}