Take a look at leetcode8 when you have time – the longest substring without repeating characters (c++ version)

Take a look at leetcode8 when you have time – the longest substring without repeating characters (c++ version)

study foreword

Exams are so hard.

topic

Given a [string] , find the length of the longest substring that does not contain repeating characters.

Example 1:

Input: “abcabcbb”
Output: 3
Explanation: Since the longest substring without repeating characters is “abc”, its length is 3.
Example 2:

Input: “bbbbb”
Output: 1
Explanation: Since the longest substring without repeating characters is “b”, its length is 1.
Example 3:

Input: “pwwkew”
Output: 3
Explanation: Since the longest substring without repeating characters is “wke”, its length is 3.

solution

class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {
        int start(0), end(0), length(0), result(0);
        int sSize = int(s.size());
        unordered_map<char, int> hash;
        while (end < sSize)
        {
            char tmpChar = s[end];
            length++;

            if (hash.find(tmpChar) != hash.end() && hash[tmpChar] >= start)
            {
                start = hash[tmpChar];
                length = end - start;
            }
            hash[tmpChar] = end;

            end++;
            result = max(result, length);
        }
        return result;
    }
};

Idea:
Use length to implement global length detection, which is used for counting when no characters are repeated.
When there is a repeated occurrence of a character, use if to judge, and the hash table saves the serial number of the last occurrence of this character.

Leave a Comment

Your email address will not be published. Required fields are marked *