Najdłuższy podciąg bez powtarzających się znaków Rozwiązanie Leetcode

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

Problem Statement

W ramach projektu Najdłuższy podciąg bez powtarzających się znaków Rozwiązanie LeetCode –  stwierdza, że ​​dany ciąg s. Musimy znaleźć najdłużej podciąg bez powtarzających się znaków.

Przykład:

Input:  s = "abcabcbb"

Output: 3

Wyjaśnienie:

• Najdłuższy podciąg bez powtarzających się znaków ma długość 3.
• Ciąg to: „abc”.

Input:  s = "bbbbb"

Output: 1

Wyjaśnienie:

• Wszystkie znaki są takie same, dlatego najdłuższy podciąg bez powtarzających się znaków ma długość 1.

Podejście

Idea:

1. Główną ideą rozwiązania tego problemu jest użycie Hashmap.
2. Możemy również użyć metody brute force, aby wziąć pod uwagę każdy podciąg i sprawdzić, czy podciąg zawiera wszystkie odrębne znaki. Podejście Brute Force da werdykt przekroczenia limitu czasu, ponieważ maksymalny rozmiar tablicy to 5 * 10^4.
3. Zachowaj hashmapę, która przechowuje znaki w ciągach jako klawisze i ich pozycje jako wartości i zachowaj dwa wskaźniki które definiują maksymalny podciąg.
4. Przesuń prawy wskaźnik, aby przejrzeć ciąg i w międzyczasie zaktualizuj hashmapę.
5. Jeśli postać jest już na hashmapie, przesuń lewy wskaźnik na prawo od ostatnio znalezionego znaku. Zauważ, że te dwa wskaźniki mogą poruszać się tylko do przodu.
6. Na koniec otrzymamy długość najdłuższego podciągu z różnymi znakami.

Kod

Najdłuższy podciąg bez powtarzających się znaków Rozwiązanie C++:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> occ(260,-2);
        int n = s.length(),ans = 0,j = 0;
        for(int i=0;i<n;i++){
            if(occ[s[i]]==-2){
                ans = max(ans,i-j+1);
            }
            else{
                while(j<=occ[s[i]]){
                    occ[s[j++]] = -2;
                }
            }
            occ[s[i]] = i;
        }
        return ans;
    }
};

Najdłuższy podciąg bez powtarzających się znaków Rozwiązanie Java:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length()==0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max=0;
        for (int i=0, j=0; i<s.length(); ++i){
            if (map.containsKey(s.charAt(i))){
                j = Math.max(j,map.get(s.charAt(i))+1);
            }
            map.put(s.charAt(i),i);
            max = Math.max(max,i-j+1);
        }
        return max;
    }
}

Analiza złożoności:

Złożoność czasowa

Złożoność czasowa powyższego kodu wynosi NA) jeśli użyjemy wektora o wystarczającym rozmiarze do śledzenia występowania znaków lub dobrej funkcji mieszającej, która umożliwia wstawianie i usuwanie w stałym czasie, gdzie N = rozmiar ciągu wejściowego.

Złożoność przestrzeni

Złożoność przestrzeni powyższego kodu wynosi O (M) gdzie M = rozmiar hashmapy. Hashmap przechowuje wpisy znaków. Złożoność kosmiczna rozwiązania całkowicie zależy od hashmapy. Złożoność przestrzeni będzie tym większa, im większy będzie rozmiar hashmapy.