Problem#
Given a string s
, find the length of the longest substring without repeating characters.
Solution 1: Sliding Window + Hash Table#
Find the maximum length#
Console.WriteLine(LengthOfLongestSubstring("abcabcbb"));
Console.WriteLine(LengthOfLongestSubstring("bbbbb"));
Console.WriteLine(LengthOfLongestSubstring("pwwkew"));
// Get the length of the longest substring without repeating characters in the given string
int LengthOfLongestSubstring(string str)
{
if (string.IsNullOrWhiteSpace(str)) return 0;
// Hash table to record the last index where the character str[right] appears
Dictionary<char, int> dic = new();
// Define the left pointer (-1 or 0), and the length of the longest non-repeating substring
int left = -1, res = 0;
// Continuously increase the right pointer to expand the window
for (int right = 0; right < str.Length; right++)
{
//Console.WriteLine($"Expand the interval to the right: [{left}, {right}]");
var currentChar = str[right];
if (dic.ContainsKey(currentChar))
{
// Continuously increase the left pointer to shrink the window, because a duplicate character is encountered, update the left pointer to the index of the duplicate value
left = dic[currentChar];
//Console.WriteLine($"Shrink the interval to the right: [{left}, {right}]");
}
// Update the hash table record: the last index where the current character appears in the string
dic[currentChar] = right;
// Update the result: subtract the right pointer from the left pointer to get the length of the closed interval with the maximum non-repeating substring
// Then use the Max function to take the maximum value between the previous round res and the width (right - left) of the current round interval [left+1, right]
res = Math.Max(res, right - left);
//Console.WriteLine($"------Result of round {right}: {res}------{Environment.NewLine}");
}
return res;
}
Find the maximum continuous substring#
Console.WriteLine($"Result: {MaxChild("abca2f")}");
Console.WriteLine($"Result: {MaxChild("aabbcc")}");
Console.WriteLine($"Result: {MaxChild("aaaaa")}");
// Longest non-repeating substring (continuous)
string MaxChild(string str)
{
if (string.IsNullOrWhiteSpace(str)) return string.Empty;
Dictionary<char, int> dic = new();
int left = 0;
string res = "";
// [left, right]
for (int right = 0; right < str.Length; right++)
{
// Current character being traversed
char currentChar = str[right];
// Whether it has appeared before, if it has appeared, reduce the left boundary to the index of the duplicate appearance
if (dic.ContainsKey(currentChar))
{
// When it is included, it means that a duplicate string appears, shrink the window
left = dic[currentChar] + 1;
//Console.WriteLine($"update {currentChar} {right}");
// Update the index
//dic[currentChar] = right;
dic.Clear();
}
dic[currentChar] = right;
// Update the result
string sub = str.Substring(left, right - left + 1);
if (sub.Length > res.Length)
{
res = sub;
}
}
return res;
}
(To be learned) Solution 2: Dynamic Programming + Hash Table#
(See K's diagram for explanation)
Reference:#
- 3. Longest Substring Without Repeating Characters - LeetCode
- Detailed explanation of sliding window: Sliding Window for Beginners - LeetCode
- K's diagram: 3. Longest Substring Without Repeating Characters - LeetCode