Сегодня в этом блоге я объясню алгоритм решения самой длинной подстроки без повторения символов, используя технику наивного и скользящего окна.

Совет для новичков: попробуйте решить задачу последовательно на листе бумаги, используя разные методы, пока не придете к разумному решению. Большинство новичков тратят много энергии на написание идеального кода и не понимают, что копирование мыслительного процесса с бумаги на компьютер - лишь минутная часть улучшения в программировании. Не забывайте проявлять терпение и не сдаваться.

Учитывая строку str, мы должны найти длину самой длинной подстроки без каких-либо повторений. Например,

if str = "abcabcbb"
3
(because "abc" is the longest substring with no repetitions)

Наивный подход заключался бы в проверке всех подстрок и проверке на каждой i-й итерации, существует ли повторяющийся символ. Пусть начальный и конечный индексы подстроки равны i and j where 0 ≤ i < j ≤ n. Переберите все символы и проверьте, существует ли новый проанализированный символ в подстроке. Чтобы проверить дублирование, создайте function checkDuplicacy, который создает набор из подстроки и проходит через него, чтобы вернуть истину или ложь.

Следовательно, используя два вложенных цикла с i от 0 до n −1 и j от i +1 до n, мы можем перечислить все подстроки s. Ниже приведен код наивного подхода:

int lenOfLongestSubstring(string s) {
    int n = s.length();
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
           if (checkDuplicacy(s, i, j))
               res = max(res, j - i + 1);
        }
    }
    return ans;
}
bool checkDuplicacy(string& s, int start, int end) {
    vector<int> chars(128);
    for (int i = start; i <= end; i++) {
        char c = s[i];
        chars[c]++;
        if (chars[c] > 1)
            return false;
    }
    return true;
}

Этот подход требует O(n³) времени, но мы можем добиться большего, используя метод скользящего окна.

Техника скользящего окна показывает, как вложенный цикл for в некоторых задачах можно преобразовать в один цикл for, чтобы уменьшить временную сложность.

В наивных подходах мы неоднократно проверяем подстроку, чтобы увидеть, есть ли в ней повторяющийся символ. Но в этом нет необходимости. Если подстрока s_ij от индекса i до j −1 уже проверена на отсутствие повторяющихся символов. Нам нужно только проверить, есть ли уже s [j] в подстроке s_ij.

Чтобы проверить, есть ли уже символ в подстроке, мы можем просканировать подстроку, что приведет к алгоритму O (n²). Но мы можем добиться большего.

Используя HashSet в качестве скользящего окна, можно проверить, можно ли использовать текущий символ в O (1).

Ниже приведены два способа реализации скользящего окна для уменьшения временной сложности с O (n³) до O (n²) и O (n) соответственно.

class Solution {
public:
    int lenOfLongestSubstring(string s) {
     
        int ans = 0;
        for (int i = 0; i < s.length(); ++i) {
            for (int j = i; j < s.length(); ++j) {
                if (repeat(s, i, j)) {
                    ans = max(ans, j-i+1);
                }
            }
        }
        return ans;
    }
    
    bool repeat (string s, int start, int end) {
        vector<int> chars(128);
        
        for (int i = start; i <= end; ++i) {
            char c = s[i];
            chars[c]++;
            if (chars[c] > 1) {
                return false;
            }
        }
        return true;
    }
};

Временная сложность: O(n²)

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> chars(128);
        int left = 0;
        int right = 0;
        int res = 0;
        while (right < s.length()) {
            char r = s[right];
            chars[r]++;
        while (chars[r] > 1) {
                char l = s[left];
                chars[l]--;
                left++;
            }
        res = max(res, right - left + 1);
        right++;
        }
    return res;
    }
};

Сложность времени: O(n)

Следите за новостями, чтобы увидеть больше этих обучающих программ по алгоритмам.