面试之算法基础系列1.最多有k个不同字符的最长子字符串

cutercorley

发布于 2021-01-05 09:54:16

4860

发布于 2021-01-05 09:54:16

文章被收录于专栏：Corley的开发笔记Corley的开发笔记

文章目录

- 1.最长子字符串

1.最长子字符串

题目原为：

【题目】给定一个字符串，给定一个数字k ( 0< k ≤ 字符串长度)，输出最长的包含k个不同字符子串的长度。【Example】 “cbca”, k=2，输出最长的包含2个不同字符子串的长度。答案：3 题目来源：百度 SRE工程师实习生一面，可点击https://www.nowcoder.com/discuss/585284查看一面凉经/(ㄒoㄒ)/~~

最容易想到的是暴力解法，就是遍历求出字符串的所有子串，并找出不同字符为k的最长字符，Python代码如下：

def find_max_substring(string, k):
    str_length = len(string)
    sub_string_list = (string[i:i + j + 1] for j in range(str_length) for i in range(str_length - j))
    length_list = []
    for sub_string in sub_string_list:
        if len(set(list(sub_string))) == k:
            length_list.append(len(sub_string))
    return max(length_list)
 
 
if __name__ == '__main__':
    string = input()
    k = int(input())
    max_length = find_max_substring(string, k)
    print(max_length)

显然，这种实现方式效率是很低的，虽然使用了生成器，但是在性能方面还是有很大的问题，同时未考虑特殊情况。后来查询了一些资料，使用了同向双指针和字典来对实现方式进行了优化：

def find_max_substring(string, k):
    str_length = len(string)
    if str_length == 0 or k == 0:
        return 0
    count = 0
    left = 0
    right = 0
    res = 0
    count_dic = {}
    while right < str_length:
        if string[right] not in count_dic or count_dic[string[right]] == 0:
            count += 1
            count_dic[string[right]] = 1
        else:
            count_dic[string[right]] += 1
        right += 1
        while count > k:
            count_dic[string[left]] -= 1
            if count_dic[string[left]] == 0:
                count -= 1
            left += 1
        res = max(res, right - left)
    return res


if __name__ == '__main__':
    string = input()
    k = int(input())
    max_length = find_max_substring(string, k)
    print(max_length)

在字符串长度为0或者k为0时直接返回0；通过使用同向双指针的方式，可以做到只遍历一次字符串就能得到答案，从而使时间复杂度为O(n)，在字符串上移动滑动窗口的两个指针，来保证窗口内的字符不超过k个，具体如下：

设置指针left、right初始位置均为0，初始化计数数组；
当right小于字符串长度时，每次判断字符s[right]是否位于计数数组中，不在则计数count加1，同时对字典进行更新，并使right指针向右移动；
- 在字符数超过k时，需要移去窗口中最左侧的字符string[left]，同时向右移动left指针使得滑动窗口只包含k个不同字符；
- 更新最大长度res = max(res, right - left)。

此时运行结果如下：