专栏首页数据分析与挖掘【python-leetcode340-滑动窗口法】至多包含 K 个不同字符的最长子串

【python-leetcode340-滑动窗口法】至多包含 K 个不同字符的最长子串

问题描述:给定一个字符串s,找到至多包含k个不同字符得最长子串的长度。

比如s="cebea",k=2,那么输出结果就是3,因为此时"ebe"满足条件:至多包含两个不同字符,且子串最长

比如s="world",k=4,那么输出结果就是4,因为"worl"和"orld"满足条件:至多包含4个不同字符,且子串最长

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s, k):
        tmp = 0 #用于记录满足条件得最大值
        for i in range(1,len(s)+1):#步长从1到len(s)+1
            for j in range(len(s)-i+1):#窗口左端
                print(s[j:j+i])
                if len(set(s[j:j+i])) == k:#如果窗口中取集合后的不同字符就是k个
                    tmp = max(tmp,i)#更新tmp的值
                    print("tmp:{}".format(tmp))
        return tmp #最后返回即可

过程:

c e b e a ce tmp:2 eb tmp:2 be tmp:2 ea tmp:2 ceb ebe tmp:3 bea cebe ebea cebea

第二种方法:

思路: 一个hash表和一个左边界标记. 遍历字符串将其加入到hash表中, 不同字符多于k个了, 就从左边开始删字符. 直到hash表不同字符长度等于k.此时字符串的长度就是当前字符和左边界的距离。

class Solution:
    def lengthOfLongestSubstringKDistinct(self,s,k):
        from collections import defaultdict
        #使用python中的collections.defaultdict
        #字典中存储的整型的值默认为0
        hash = defaultdict(int)
        max_num = 0 #用于存放最大值
        start = 0 #滑动窗口的左端
        #从字符串左开始遍历
        for i in range(len(s)):
            #遍历到一个字符,使得字典中对应得字符加1
            hash[s[i]] += 1
            while len(hash)>k:
                hash[s[start]] -= 1
                if hash[s[start]] == 0:
                    del hash[s[start]]
                start += 1
            max_num = max(max_num,i-start+1)
        return max_num

由于leetcode没会员,不能解锁,不能保证能过。但思路应该没问题。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【python-leetcode03-滑动窗口法】无重复字符的最大子串

    输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。 示例 2:

    绝命生
  • golang数据结构之循环链表

    绝命生
  • python实现支持向量机之非线性支持向量机和核函数(理论五)

    比如说图7-7,左图中的数据是线性不可分的,利用非线性变换将其转换为右图中的数据分布,再利用线性支持向量机就可以解决了。

    绝命生
  • Java知识点——xml概述

    用户7073689
  • 1. C语言的第一个程序

    (。・∀・)ノ゙嗨!大家好,我是呆博~很开心可以在这里给大家分享我的 C 语言学习笔记~

    谭庆波
  • Python 计算一年有多少秒

    py3study
  • 论文阅读学习 - Deep Representation Learning with Target Coding

    1-of-K code:长度为 KKK 的向量,第 kkk 个元素为 1,其它的为 0. [分类任务]

    AIHGF
  • 内功修炼-算法02

    在做这道题目的过程中,没有考虑到空格字符串的情况,这是基础不扎实导致的,null/“”/“ “,这三个还是有很大的区别的,如果大家也遇到和我一样的问题,可以当做...

    Share猿
  • httpclient访问https

    本文从spring cloud netflix zuul里头摘出httpclient访问https/http的源码,展示一下怎么用httpclient去访问ht...

    codecraft
  • 生物信息学技能面试题(第4题)-多个同样的行列式文件合并起来

    相信用过htseq-count的朋友都知道,它是分开对每个样本计算所有的基因表达量,所以会生成一个个独立的文件,我用perl脚本模仿它的结果如下: $ head...

    生信技能树

扫码关注云+社区

领取腾讯云代金券