基本信息

  • 题号：763
  • 题厂：脸书
  • 难度系数：中


已知一个字符串，要把字符串分组。分组后实现单个字符只出现在一个小组里，即：单个字符不会跨组出现。。。。。。分组原则：要尽可能多分组。。。。。。

例如 s = "ababcbacadefegdehijhklij"
返回 [9,7,8]

分组结果为："ababcbaca", "defegde", "hijhklij"，返回数字分别对应分组后 substring 的长度。。。。。。
虽然"ababcbacadefegde", "hijhklij" 也满足单个字符不串组，但是没有满足尽可能多分组原则，因此不能作为正确答案。。。。。。


解题思路

  • 欲解此题，需要查询单个字符「第一次」和「最后一次」出现的 index 值，以此判断substring 可以 span 的区间
class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        # 创建 lastIndex hashmap，记录单个字符最后一次出现的 index
        # 「字符」：「last index position」
        lastIndex = {}
        for i, c in enumerate(s):
            lastIndex[c] = i
        
        # size：记录当前小组的长度
        # end：记录小组可以 span 的最后位置。。。。    
        res = []
        size, end = 0, 0
        for i, c in enumerate(s):
            # 如果当前字符最后一次出现的 index 值大于当前 end，则 end 需要后移至 lastIndex[c]
            size += 1
            end = max(end, lastIndex[c])
            
            # 如果当前 index 和 end 相等，说明到达小组末端，可以分组
            # 此时忘 res 添加当前小组长度，同时 size 清零用于下一周期
            if i == end:
                res.append(size)
                size = 0
                
        return res


Constraints

  • 1 <= s.length <= 500
  • s consists of lowercase English letters.


Big O

  • 时间复杂度：O（n）
  • 空间复杂度：O（1）。字符串中只出现 26 个小写英文字母，所以 hashmap 的长度最多为 26——是一个常数。。。。。。



测试

  • 字符串为 1 时
  • 当字符串不能出现分组时。。。。。。

……


总结

  • 词穷 😭