Lets check out the third problem listed on the Leetcode website!
The task is to find the length of the longest substring without any repeating characters. This requires iterating through the string, keeping track of the current substring and its length, and updating the length when a repeating character is encountered.
One common approach to solve this problem is to use the sliding window technique. Maintain two pointers (start and end) that define the current substring. Move the end pointer to include new characters, and if a repeating character is found, move the start pointer to the right until the substring becomes valid again. Keep track of the maximum length encountered during this process.
public int LengthOfLongestSubstring(string s)
{
int n = s.Length;
int maxLength = 0;
int start = 0;
Dictionary<char, int> charIndexMap = new Dictionary<char, int>();
for (int end = 0; end < n; end++)
{
if (charIndexMap.ContainsKey(s[end]) && charIndexMap[s[end]] >= start)
{
// If the character is repeated, update the start pointer to the right
start = charIndexMap[s[end]] + 1;
}
charIndexMap[s[end]] = end;
maxLength = Math.Max(maxLength, end - start + 1);
}
return maxLength;
}
This LengthOfLongestSubstring
method takes a string s
as input and returns the length of the longest substring without repeating characters.
Here’s a brief explanation of the key parts of the code:
start
and end
, to define the current substring.charIndexMap
dictionary is used to store the index of each character’s last occurrence in the string.start
pointer when a repeating character is encountered.maxLength
variable with the length of the current valid substring.This solution has a time complexity of O(n), where n is the length of the input string s
, making it an efficient approach for this problem.
Solving the Leetcode problem “Longest Substring Without Repeating Characters” problem involves efficiently traversing the string and maintaining a substring without any repeating characters. The sliding window approach is a popular and efficient strategy for solving such substring-related problems.
Inserting elements into an array dynamically is a common operation in C# programming, especially when…
Utilizing GPUs (Graphics Processing Units) can significantly accelerate certain computational tasks, particularly those involving parallel…
Utilizing the "Like" operator in C# LINQ (Language-Integrated Query) allows you to perform pattern matching…
Adding dropdown lists to your ASP.NET MVC application can enhance user experience and provide a…
In programming, countdowns are often essential for various applications, from simple timers to more complex…
Choosing what docker compose version to Use is crucial for ensuring compatibility and maximizing performance…
View Comments
Its like you read my mind! You seem to know so much about this,
like you wrote the book in it or something.
I think that you can do with some pics to drive the message home a bit,
but other than that, this is excellent blog. An excellent read.
I'll certainly be back.
Hello There. I found your blog using msn. This is an extremely well written article.
I will be sure to bookmark it and come back to read more
of your useful info. Thanks for the post. I will definitely comeback.