eli和字符串

# -*- coding: utf-8 -*-

import collections


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param str string字符串
# @param k int整型
# @return int整型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/0259119d24ca40b897218f09137e4be2?tpId=196&tqId=40550&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    算法：
        题目要求：计算字符串str中包含k个相同字符的最短子串，str中仅包含小写字母。所以我们枚举"a" - "z"中每个字符，统计包含k个该字符的最短子串。
        使用哈希表posMp存储每个字符出现的所有下标，如果字符出现次数刚好为k，更新结果res并移除左边界
    复杂度：
        时间复杂度：O(n)，n为字符串str的长度
        空间复杂度：O(n)，哈希表的辅助空间
    """

    def eliStr(self, str, k):
        # write code here
        posMp = collections.defaultdict(list)

        res = len(str) + 1
        for i, ch in enumerate(str):
            posMp[ch].append(i)
            if len(posMp[ch]) == k:  # 找到包含k个相同字符ch的子串，更新res
                res = min(res, i - posMp[ch][0] + 1)
                posMp[ch].pop(0)
        return -1 if res == len(str) + 1 else res


if __name__ == "__main__":
    sol = Solution()

    str, k = "abeba", 2

    res = sol.eliStr(str, k)

    print res