Find the maximum non-repeating substring in a string (calculate the length and the longest substring).

Problem#

Given a string s, find the length of the longest substring without repeating characters.

Solution 1: Sliding Window + Hash Table#

Info

💡 Sliding Window: A variable-sized window that slides forward in the same direction (fixed at the right end, sliding at the left end). It can be imagined as a queue, with one end pushing and the other end popping elements.

Idea:

Use the "left-right pointer" technique in the sequence, initialize left = right = 0, and call the index closed interval [left, right] a window.
First, continuously increase the right pointer to expand the window until the sequence in the window meets the requirements.
At this point, stop increasing the right pointer and instead continuously increase the left pointer to shrink the window until the sequence in the window no longer meets the requirements. At the same time, update the result before each increase in the left pointer.
Repeat steps 2 and 3 until the right reaches the end of the sequence.

Step 2 is equivalent to finding a feasible solution, and step 3 is optimizing the feasible solution, finally finding the optimal solution. The left and right pointers advance alternately, the window size increases and decreases, and the window slides to the right.

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