00003. Leetcode: Longest Substring Without Repeating Characters – Problem and Solution

Lets check out the third problem listed on the Leetcode website!

Problem Analysis

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.

Approach

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.

Solution

 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:

• We use two pointers, start and end, to define the current substring.
• The charIndexMap dictionary is used to store the index of each character’s last occurrence in the string.
• We iterate through the string, updating the start pointer when a repeating character is encountered.
• We update the 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.

Conclusion

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.