C# solution: Dictionary + HashSet + dp (not efficient)


  • 0
    B
    public class Solution 
    {
    	public int LongestSubstring(string s, int k)
    	{
    		if (k == 1) return s.Length;
    
    		var dp = new int[s.Length + 1];
    
    		var globalLongest = 0;
    
    		for (int i = k - 1; i < s.Length; i++)
    		{
    			var charAndCount = new Dictionary<char, int>();
    			var curCharHashSet = new HashSet<char>();
    			var localLongest = 0;
                
    			for (int j = i; j >= 0; j--)
    			{
    				var curChar = s[j];
    
    				if (charAndCount.ContainsKey(curChar))
    				{
    					charAndCount[curChar]--;
    
    					if (charAndCount[curChar] == 0)
    					{
    						charAndCount.Remove(curChar);
    						curCharHashSet.Add(curChar);
    
    						if (charAndCount.Count == 0)
    						{
    							localLongest = i - j + 1 + dp[j+1-1];
    							j -= dp[j+1-1];
    							
    						}
    					}
    				}
    				else
    				{
    					if (!curCharHashSet.Contains(curChar))
    					{
    						charAndCount[curChar] = k - 1;
    					}
    					else if (charAndCount.Count == 0)
    					{
    						localLongest = i - j + 1 + dp[j+1-1];
    						j -= dp[j+1-1];
    					
    					}
    				}
    			}
                
                dp[i+1] = localLongest;
    			globalLongest = Math.Max(globalLongest, localLongest);
    		}
    
    		return globalLongest;
    	}
    }
    

Log in to reply
 

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