myesn

myEsn2E9

hi
github

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#

image

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:#

Loading...
Ownership of this post data is guaranteed by blockchain and smart contracts to the creator alone.