Longest Substring Without Repeating Characters

Programming Language: C++

Back to Leetcode Blind 75 Practice Note

Leetcode: Longest Substring Without Repeating Characters

看別人解答才知道怎麼寫這題。
還有一些寫法無法理解

這次學習到幾個之前沒用過的C++用法：

1. size(): 回傳array元素個數
2. unordered_map
3. count()
4. max()
5. window sliding(用來檢查是否有重複字元)

先看解答，如下，解答後詳細說明

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int charCount       = s.size();
        int outSubstringCnt = 0;

        unordered_map<char, int> charMap;
        int left = 0;

        for (int right = 0; right < charCount; right++)
        {
            if ( charMap.count(s[right]) == 0 || charMap[s[right]] < left )
            {
                charMap[s[right]] = right;
                outSubstringCnt = max(outSubstringCnt, right - left + 1);
            }
            else
            {
                left = charMap[s[right]] + 1;
                charMap[s[right]] = right;
            }
        }

        return outSubstringCnt;
    }
};

以下詳細說明：

1. size(): 回傳array元素個數

但無法用在int array，可以用在string和vector(任何型態皆可用，包含vector<int>)

解答中的用法如下：
計算共有幾個字母

int charCount       = s.size();

C++中，size()和length()是一樣的。
範例如下：

#include <iostream>
using namespace std;
int main() {

    string str = "abcdefg";
    int A = str.size();
    int B = str.length();
    
    // Output: A = 7, B = 7
    cout << "A = " << A << endl;
    cout << "B = " << B << endl;

    return 0;
}

2. unordered_map

這篇教學寫得很好，可以參考。

unordered_map 容器插入元素有兩種寫法，
第一種是使用中括號 [] 的方式來插入元素，很像陣列的寫法，例如：umap[key] = value，範例如下

std::unordered_map<std::string, int> umap;
...
umap["John"] = 3;

在這題使用unordered_map來實現slide window的演算法，我覺得好難理解，應該是slide window的code看太少了。

3. count()

統計個數

4. max()

取最大值

5. window sliding(用來檢查是否有重複字元)

To be updated.