Skip to content

Instantly share code, notes, and snippets.

@AmSmart
Last active August 21, 2020 22:17
Show Gist options
  • Save AmSmart/d7faae1ed4237eb546f5dbbc96ecbacb to your computer and use it in GitHub Desktop.
Save AmSmart/d7faae1ed4237eb546f5dbbc96ecbacb to your computer and use it in GitHub Desktop.
Returns the length of the longest continuous substring of a string with no repeated character (C# &Python)
public int LengthOfLongestSubstring(string s)
{
// Dictionary to keep track of valid substrings and their length
var substringDict = new Dictionary<string, int>();
for(int i = 0; i < s.Length; i++)
{
// Dictionary to detect if any character is being repeated
// This should have been an HashSet😒 as the value in each pair is a dummy
var reptDetector = new Dictionary<char, int>();
string x = s.Substring(i);
for(int j = 0; j < x.Length; j++)
{
try
{
reptDetector.Add(x[j],1);
}
catch
{
// If current character is a repetition, make x the last valid substring
// and break out of the loop
x = x.Substring(0,j);
break;
}
}
// Add substring to dictionary only when the key is new
if(!substringDict.ContainsKey(x))
{
substringDict.Add(x,x.Length);
}
}
// Return 0 if dictionary is empty, else, return the max value
return substringDict.Count > 0 ? substringDict.Select(x => x.Value).Max() : 0;
def lengthOfLongestSubstring(s):
# Dictionary to keep track of valid substrings and their length
substrings_dict = {}
for i in range(len(s)):
# Dictionary to detect if any character is being repeated
# This should have been an HashSet😒 as the value in each pair is a dummy
rept_detector_dict = {}
x = x[i:]
for j in range(len(x)):
try:
rept_detector_dict[x[j]] = 1
except:
# If current character is a repetition, make x the last valid substring
# and break out of the loop
x = x[j:]
break
# Add substring to dictionary only when the key is new
if x in substrings_dict.keys() == False:
substrings_dict[x] = len(x)
# Return 0 if dictionary is empty, else, return the max value
if len(substrings_dict) == 0:
return 0
return max(substrings_dict.values())
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment