划分字母区间

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


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param s string字符串
# @return int整型一维数组
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/3a54a4f5bfa14891adb55484519210be?tpId=196&tqId=40445&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    参考：
        大神：牛客683289936号
    算法：
        本题要求对字符串进行尽可能多的划分，但是要求如果出现相同字符，那么该字符所包含的区间必须划分到一起，比如"abba", 划分后为[4]
        首次遍历字符串s：
            建立哈希表hashMap，键为s中的字符，值为该字符最后一次出现的下标
        再次遍历字符串s：
            使用start、end分别记录待截取区间的左右边界，其中end更新为包含重复元素的最远右边界
            当i与end相遇，就需要进行区间截取，同时更新start
    复杂度：
        时间复杂度：O(n), n为字符串s的长度
        空间复杂度：O(m), m为不重复的字符数量
    """

    def splitString(self, s):
        # write code here
        n, hashMap = len(s), {}

        for i in range(n): # 哈希表记录每个字符最后一次出现的下标
            hashMap[s[i]] = i
        # print hashMap

        start, end, res = 0, -1, []
        for i in range(n):
            end = max(end, hashMap[s[i]]) # end更新为包含重复元素的最远边界
            if i == end: # 访问到右边界，需要进行区间截取
                res.append(end - start + 1)
                start = i + 1
        return res


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

    s = "anfjaklii"

    # s = "abba"

    # s = "abcabc"

    # s = "abcac"

    res = sol.splitString(s)

    print res