Egbert Lin's Blog

“Life is not a race, but a journey to be savoured each step of the way” by Brian Dyson

[LeetCode Road] Longest Substring Without Repeating Characters - Solution/C++

Posted on Edited on In Disqus:

3. Longest Substring Without Repeating Characters

Question:

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

Example:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Input: s = ""
Output: 0

Constraints:
  • 0 <= s.length <= 5 * 104
  • span style="background-color:#F0F0F0">s consists of English letters, digits, symbols and spaces.

    • Source code

    Version 1

    Idea:
    It is a brute force to check every character for finding a valid longest string.
    At 9 line, a declaration of the vector is 128 sizes with all NULL. Then, let j = i and find the end of character whish has a longest string. So, at 11-12 line, use a while to consist two constraints: 1) j must be smaller than n and 2) arr[s[i]] must be NULL, if true, it should add 1 and j++. If false, it means a character has shonw already, therefore, go to 14 line and calculate the length of string.

    Time complexity: O(n*128)
    Space complexity: O(128)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            if(s.length() == 0) return 0;
            
            const int n = s.length();
            int maxLen = 0;
            for(int i = 0; i < n; i++){
                vector<int> arr(128);
                int j = i;
                while(j < n && !arr[s[j]]){
                    arr[s[j++]] ++;
                }
                maxLen = max(maxLen, j - i);
            }
            return maxLen;
        }
    };

    Version 2

    Idea:
    It is a hash table's concept with sliding window principle. This method is refered to Huahua’s Tech Road.
    There are two necessary indexes, i and j.

    i represents the start index of valid string.
    j represents the moving index to increasing window size.
    // Window size: through the string

    The demonstration is shown as below:

    At 11 line, it means getting a start index and ensure a valid string. E.g., at the begining, vector's values are -1. So, i always is 0 (-1 + 1). If a charactor has exist in vector already when j increases, avoid the same chararcors in string, therefore, i will be 1 (0 + 1). // move one position

    At 12 line, use current j index to calculate the length of string between j and i. Notice, plus 1 at j - i + 1 is very important, it should counts the element of i index.

    At 13 line, record the element's position to know where it is last position in string.

    Time complexity: O(n)
    Space complexity: O(128)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            const int n = s.length();
            
            vector<int> arr(128, -1); // All characters of ASCII table
            int res = 0;
            
            for(int i = 0, j = 0; j < n; j++){
                i = max(i, arr[s[j]] + 1); // Get the position of i index
                res = max(res, j - i + 1); // Get the valid maximum length
                arr[s[j]] = j; // Recode the current position of s[j] character
            }
            return res;
        }
    };