LeetCode/LeetCode-3.cpp at master · hello-sources/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*************************************************************************
    > File Name: LeetCode-3.cpp
    > Author: ltw
    > Mail: 3245849061@qq.com
    > Created Time: Sat 16 May 2020 08:35:16 PM CST
 ************************************************************************/

#include <iostream>
using namespace std;

class Solution {
public:
    bool check(string &s, int l) {
        int cnt = 0;
        int arr[256] = {0};
        for (int i = 0; s[i]; i++) {
            arr[s[i]] += 1;
            if (arr[s[i]] == 1) cnt += 1;
            if (i >= l) {
                arr[s[i - l]] -= 1;
                if (arr[s[i - l]] == 0) cnt -= 1;
            }
            if (cnt == l) return 1;
        }
        return 0;
    }

    int bs(string &s, int l, int r) {
        if (l == r) return l;
        int mid = (l + r + 1) >> 1;
        if (check(s, mid)) return bs(s, mid, r);
        else return bs(s, l, mid - 1);
    }
    int lengthOfLongestSubstring(string s) {
        if (s == "") return 0;
        return bs(s, 1, s.size());
    }
};