Leetcode - 3 найти самую длинную подстроку без повторения символа

Question

Цель проста - найти самую длинную подстроку без повторяющихся символов, вот код:

 class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ans = 0;
        int dic[256];
        memset(dic, -1, sizeof(dic));
        int len = s.size();
        int idx = -1;

        for (int i = 0;i < len;i++) {
            char c = s[i];
            if (dic[c] > idx)
                idx = dic[c];

            ans = max(ans, i - idx);

            dic[c] = i;
        }
        return ans;
    }

};

Из его краткого выражения я думаю, что это высокопроизводительный метод, и мы можем получить, что его временная сложность равна просто O (n). Но я запутался в этом методе, хотя я придумал несколько примеров, чтобы Понимаете, кто-нибудь может дать мне несколько советов или идей?

Answer 1

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

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

Я уверен, что код кода ans = max() будет немного оптимизирован, так как после обнаружения нового дубликата вы должны продвинуться по крайней мере вперед с момента запуска этого дубликата, прежде чем можно будет снова улучшить ответ.Вы все еще должны выполнить остальную часть работы, поддерживая dic и idx, но вы можете избежать этого конкретного теста для ans в течение нескольких итераций.Однако, чтобы извлечь выгоду, вам придется много разучиться.