跳转至

159. 至多包含两个不同字符的最长子串

最后更新：2024-05-10-22

链接：https://leetcode.cn/problems/longest-substring-with-at-most-two-distinct-characters/description/

解题思路

可以用暴力直接去解决

  1. 先确定滑窗的left不动，right向右移动，移动的过程中，找到a，b两个字符
  2. 当right既不是a也不是b的时候，说明我们找到了一个窗口，计算当前窗口的长度，并与max比较；
  3. 移动left，直到a或者b全部移出当前窗户后，继续下一个循环
C
 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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#define MAX(a, b) ((a) > (b) ? (a) : (b))

void moveSlidingWindowsLeftFrame(char *in_a, int *num_a, char *in_b, int *num_b, char **left)
{
    char *pos  = *left;
    int count_a = *num_a;
    int count_b = *num_b;

    // 窗口左侧移动，直到a或者b全部移出窗口
    while ((count_a != 0) && (count_b != 0)) {
        if (*pos == *in_a) {
            count_a--;
        }

        if (*pos == *in_b) {
            count_b--;
        }
        pos++;
    }

    *num_a = count_a;
    *num_b = count_b;
    // a全部移动出去，b不变，下次循环需要找下一个a
    if (count_a == 0) {
        *in_a = '\0';
    } else {
        // b全部移动出去，则a不变，继续找下一个b
        *in_b = '\0';
    }

    *left = pos;
}

bool counterString(char *s, char **pos, int *nums)
{
    char *tmp = *pos;
    // 取a
    if (*s == '\0') {
        *s = *tmp;
    }
    // 字符a计数
    if (*tmp == *s) {
        (*nums)++;
        *pos = tmp + 1;
        return true;
    }

    return false;
}

int lengthOfLongestSubstringTwoDistinct(char * s)
{
    char *left = s;
    char *right = s;
    int num_a = 0;
    int num_b = 0;
    int max = 0;

    char a = '\0';
    char b = '\0';
    while ((left <= right) && (*left != '\0') && (*right != '\0')) {
        // 取a或者b
        if (counterString(&a, &right, &num_a) || counterString(&b, &right, &num_b)) {
            continue;
        }

        // 不是a，也不是b，说明取得了一个窗口，计算最大值
        max = MAX(max, num_a + num_b);
        moveSlidingWindowsLeftFrame(&a, &num_a, &b, &num_b, &left);
    }

    return MAX(max, num_a + num_b);
}
Go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func lengthOfLongestSubstringTwoDistinct(s string) int {
    m := make(map[byte]int)
    l, r := 0, 0
    var res int
    for r < len(s) {
	    if len(m) <= 2 {
		    m[s[r]]++
		    if len(m) <= 2 {
			    sum := r - l + 1
			    if res < sum {
				    res = sum
			    }
		    }
		    r++
	    } else {
		    m[s[l]]--
		    if m[s[l]] == 0 {
			    delete(m, s[l])
		    }
		    l++
	    }
    }
    return res
}