Самая длинная подстрока без повторяющихся символов · Покажи мне свой код

Для заданной строки найдите длину самой длинной подстроки без повторяющихся символов.

Примеры:

Учитывая "abcabcbb", ответ будет "abc", длина которого равна 3.

Учитывая "bbbbb", ответ "b" с длиной 1.

Учитывая "pwwkew", ответ будет "wke" с длиной 3. Обратите внимание, что ответ должен быть подстрокой, "pwke" — это подпоследовательность, а не подстрока.

Думай вслух:

Мы хотим найти самую длинную подстроку без повторяющихся символов. Первое, что приходит мне на ум, это то, что нам нужна хэш-таблица для хранения каждого символа в подстроке, чтобы при появлении нового символа мы могли легко узнать, находится ли этот символ уже в подстроке или нет. Я называю это как valueIdxHash. Затем подстрока имеет startIdx и endIdx. Итак, нам нужна переменная для отслеживания начального индекса подстроки, и я называю ее startIdx. Предположим, мы находимся в индексе i и у нас уже есть подстрока (startIdx, i - 1). Теперь мы хотим проверить, может ли эта подстрока продолжать расти или нет.

Если valueIdxHash содержит str[i], это означает, что это повторяющийся символ. Но нам еще нужно проверить, есть ли этот повторяющийся символ в подстроке (startIdx, i - 1). Поэтому нам нужно получить индекс str[i], который появился в последний раз, а затем сравнить этот индекс с startIdx.

  • Если startIdx больше, это означает, что последнее появившееся str[i] находится за пределами подстроки. Таким образом, подстрока может продолжать расти.
  • Если startIdx меньше, это означает, что последнее появившееся str[i] находится внутри подстроки. Таким образом, подстрока больше не может расти. startIdx будет обновлено как valueIdxHash[str[i]] + 1, а новая подстрока (valueIdxHash[str[i]] + 1, i) может продолжать расти.

Если valueIdxHash не содержит str[i], подстрока может продолжать расти.

Покажи мне свой код:

JavaScript

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    const valueIdxHash = {};
    var longest = 0;
    var startIdx = 0;
    for(var i = 0; i < s.length; i++) {
        if(s[i] in valueIdxHash) { //constain s[i]
            var lastAppearanceIdx = valueIdxHash[s[i]];

            if (lastAppearanceIdx < startIdx) {
                //does nothing
            } else {
                startIdx = lastAppearanceIdx + 1;
            }

            valueIdxHash[s[i]] = i;
        } else { //does not contain s[i]
            valueIdxHash[s[i]] = i;            
        }

        longest = Math.max(longest, i - startIdx + 1);
    }
    return longest;
};

//simplified version
var lengthOfLongestSubstring = function(s) {
    const valueIdxHash = {};
    var longest = 0;
    var startIdx = 0;
    for(var i = 0; i < s.length; i++) {
        if(s[i] in valueIdxHash) {
            startIdx = Math.max(startIdx, valueIdxHash[s[i]] + 1);
        }
        valueIdxHash[s[i]] = i;
        longest = Math.max(longest, i - startIdx + 1);
    }
    return longest;
};

cpp

int lengthOfLongestSubstring(string s) {
     if(s.size() <= 1)
         return s.size();

     unordered_map<int, int> value_idx_hash;//key is element, val is its index;
     int startIdx = 0;
     int longest = 0;

     for(int i = 0; i < s.size(); i++){
        if(value_idx_hash.find(s[i]) != value_idx_hash.end()){
            startIdx = max(startIdx, value_idx_hash[s[i]]+1);
        }
        value_idx_hash[s[i]] = i;

        longest = max(longest, i - startIdx + 1);
     }
     return longest;
 }

Первоначально опубликовано на algorithm.pingzhang.io.