C# O(n) Solution (Beats 95%)


  • 0
    K

    Solved in about 5 minutes. Basically, map each char to an index in a dictionary. At the same time, record the start index of the substring we're checking (to see which dictionary values to ignore). If its a unique char, add it. If non-unique, start a new substring from index + 1 of where that character was last found.

    public class Solution {
        public int LengthOfLongestSubstring(string s) {
            Dictionary<char,int> dict = new Dictionary<char,int>();
            int maxLength = 0;
            int length = 0;
            int indexStart = 0;
            
            for(int i = 0; i < s.Length; i++){
                // Unique char found
                if(!dict.ContainsKey(s[i]) || dict[s[i]] < indexStart){
                    length++;
                    dict[s[i]] = i;
                }
                // Non-unique char
                else{
                    indexStart = dict[s[i]] + 1;
                    length = i - indexStart + 1;
                    dict[s[i]] = i;
                }
                
                maxLength = Math.Max(maxLength, length);
            }
            
            return maxLength;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.