C# Accepted solution using DP


  • 0
    J
    public int LengthOfLongestSubstring(string s) 
        {
            s = s.Trim();
            if (string.IsNullOrEmpty(s)) return 0;
            if (s.Length == 1) return 1;
            
            var array = new int[s.Length];
            var max = 0; var previndex = 0;
            var dic = new Dictionary<char, int>();
            dic.Add(s[0],0);
            array[0] = 1;
            for (int i = 1; i < s.Length; i++)
            {
                if (s[i] == s[i-1])
                {
                    dic.Clear();
                    array[i] = 1;
                    dic.Add(s[i],i);
                }
                else if (dic.ContainsKey(s[i]))
                {
                    if (dic[s[i]] >= previndex)
                    {
                        array[i] = i - dic[s[i]];
                        previndex = dic[s[i]];
                        dic[s[i]] = i;
                    }
                    else
                    {
                        array[i] = array[i-1] + 1;
                        dic[s[i]] = i;
                    }
                    
                }
                else
                {
                    array[i] = array[i-1] + 1;
                    dic.Add(s[i],i);
                }
            }
            
            foreach (var num in array)
            {
                max = Math.Max(max, num);
            }
            return max;
        }
    

  • 0
    J

    @jsrikrish but I personally think cbmbbz 's solution is better. He/she used a hashmap to store the values and their index positions as well, but instead of using an array to store DP values, used two pointers.


Log in to reply
 

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