2213：由单个字符重复的最长子字符串（2628 分）

2022-03-20 约 1038 字预计阅读 3 分钟次阅读

力扣第 285 场周赛第 4 题

题目

给你一个下标从 0 开始的字符串 s 。另给你一个下标从 0 开始、长度为 k 的字符串 queryCharacters ，一个下标从 0 开始、长度也是 k 的整数下标数组 queryIndices ，这两个都用来描述 k 个查询。

第 i 个查询会将 s 中位于下标 queryIndices[i] 的字符更新为 queryCharacters[i] 。

返回一个长度为 k 的数组 lengths ，其中 lengths[i] 是在执行第 i 个查询之后 s 中仅由 单个字符重复 组成的 最长子字符串 的长度。

示例 1：

输入：s = "babacc", queryCharacters = "bcb", queryIndices = [1,3,3]
输出：[3,3,4]
解释：
- 第 1 次查询更新后 s = "bbbacc" 。由单个字符重复组成的最长子字符串是 "bbb" ，长度为 3 。
- 第 2 次查询更新后 s = "bbbccc" 。由单个字符重复组成的最长子字符串是 "bbb" 或 "ccc"，长度为 3 。
- 第 3 次查询更新后 s = "bbbbcc" 。由单个字符重复组成的最长子字符串是 "bbbb" ，长度为 4 。
因此，返回 [3,3,4] 。

示例 2：

输入：s = "abyzz", queryCharacters = "aa", queryIndices = [2,1]
输出：[2,3]
解释：
- 第 1 次查询更新后 s = "abazz" 。由单个字符重复组成的最长子字符串是 "zz" ，长度为 2 。
- 第 2 次查询更新后 s = "aaazz" 。由单个字符重复组成的最长子字符串是 "aaa" ，长度为 3 。
因此，返回 [2,3] 。

提示：

1 <= s.length <= 10⁵
s 由小写英文字母组成
k == queryCharacters.length == queryIndices.length
1 <= k <= 10⁵
queryCharacters 由小写英文字母组成
0 <= queryIndices[i] < s.length

相似问题：

分析

#1

单点更新、区间查询，可以用线段树
为了合并，需要区间的最长重复前缀和最长重复后缀

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63


class Seg:
    def __init__(self,n):
        N = 1<<n.bit_length()
        self.t = [[0]*6 for _ in range(N*2)] 
        self.n = n

    def apply(self,o,x):       
        self.t[o] = [1,x,1,x,1,1] # 最长重复前缀及字符，最长重复后缀及字符，区间长度，最长重复子串

    def merge(self,a,b):       
        res = [a[0],a[1],b[2],b[3],a[4]+b[4],max(a[5],b[5])]
        if a[3]==b[1]:
            res[5] = max(res[5],a[2]+b[0])
            if a[0]==a[4]:
                res[0] = a[0]+b[0]
            if b[2]==b[4]:
                res[2] = a[2]+b[2]
        return res

    def build(self,A,o=1,l=0,r=None):
        r = self.n-1 if r is None else r
        if l==r:
            self.apply(o,A[l])
            return
        m = (l+r)//2
        self.build(A,o*2,l,m)
        self.build(A,o*2+1,m+1,r)
        self.pull(o)

    def pull(self,o):
        self.t[o] = self.merge(self.t[o*2],self.t[o*2+1])

    def modify(self,a,x,o=1,l=0,r=None):
        r = self.n-1 if r is None else r
        if l==r:
            self.apply(o,x)
            return
        m = (l+r)//2
        if a<=m: self.modify(a,x,o*2,l,m)
        else: self.modify(a,x,o*2+1,m+1,r)
        self.pull(o)
        
    def query(self,a,b,o=1,l=0,r=None):
        r = self.n-1 if r is None else r
        if a<=l and r<=b:
            return self.t[o]
        res = self.t[0]
        m = (l+r)//2
        if a<=m: res = self.query(a,b,o*2,l,m)
        if m<b: res = self.merge(res,self.query(a,b,o*2+1,m+1,r))
        return res

class Solution:
    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:
        A = [ord(c)-ord('a') for c in s]
        n = len(A)
        seg = Seg(n)
        seg.build(A)
        res = []
        for i,c in zip(queryIndices,queryCharacters):
            seg.modify(i,ord(c)-ord('a'))
            res.append(seg.t[1][5])
        return res

4657 ms

#2

也可以用珂朵莉树，维护连续区间和长度

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


from sortedcontainers import SortedList
class Solution:
    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:
        def pop(i):
            l,r,v = sl.pop(i)
            ss.remove(r-l+1)
            return l,r,v
        def add(l,r,v):
            sl.add((l,r,v))
            ss.add(r-l+1)
        def split(x):
            i = sl.bisect_left((x,))
            if i<len(sl) and sl[i][0]==x:
                return i
            l,r,v = pop(i-1)
            add(l,x-1,v)
            add(x,r,v)
            return i
        A = [ord(c)-ord('a') for c in s]
        n = len(A)
        sl = SortedList()
        ss = SortedList()
        i = 0
        for c,g in groupby(A):
            k = len(list(g))
            sl.add((i,i+k-1,c))
            ss.add(k)
            i += k
        res = []
        for l,c in zip(queryIndices,queryCharacters):
            c = ord(c)-ord('a')
            if c!=A[l]:
                A[l] = c
                r = l
                i,j = split(l),split(r+1)
                pop(i)
                if i<len(sl) and sl[i][2]==c:
                    r = pop(i)[1]
                if i>0 and sl[i-1][2]==c:
                    l = pop(i-1)[0]
                add(l,r,c)
            res.append(ss[-1])
        return res

3701 ms

目录

2213：由单个字符重复的最长子字符串（2628 分）

题目

分析

#1

#2

解答