[Leetcode] 3 - Longest Substring Without Repeating Characters

1100 ワード

原題リンク:https://oj.leetcode.com/problems/longest-substring-without-repeating-characters/
2つのindex,left,right,すなわち通常1つのウィンドウを維持する方法である.rightが1進むたびに、現在のrightが指すcharが前に現れなければ、前進を続けます.現在rightが指すcharが現れた場合(このcharをcと呼ぶと仮定)、leftをcが現れたindex+1の位置に移動する.その後rightを増やし続けます.
*注意文字は英字のみではありません
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> arr(256);
        for (int i = 0; i < arr.size(); ++i) {
            arr[i] = -1;
        }
        
        if (s.size() == 0) return 0;
        int left = 0;
        int right = 0;
        
        int maxLen = 0;
        while (right < s.size()) {
            if (arr[s[right]] != -1) {
                int newLeft = arr[s[right]] + 1;
                while (left < newLeft) {
                    arr[s[left]] = -1;
                    left++;
                }
            } else {
                maxLen = max(maxLen, right - left + 1);
            }
            
            arr[s[right]] = right;
            right++;
        }
        
        return maxLen;
    }
};