2213. 单一重复字符的最长子串

Hard

题目描述

给你一个下标从 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^5
s 由小写英文字母组成
k == queryCharacters.length == queryIndices.length
1 <= k <= 10^5
queryCharacters 由小写英文字母组成
0 <= queryIndices[i] < s.length

解题思路

这是一道线段树的经典应用题。我们需要在每次单点更新后快速查询全局最长重复字符子串。

核心思路：

对于线段树的每个节点，我们需要维护以下信息：

左字符 (leftChar)：区间最左边的字符
右字符 (rightChar)：区间最右边的字符
左前缀长度 (leftLen)：从左端点开始的最长重复字符子串长度
右后缀长度 (rightLen)：从右端点开始的最长重复字符子串长度
区间最大值 (maxLen)：整个区间内最长重复字符子串长度

合并规则： 当合并左右两个子区间时：

如果左区间的右字符等于右区间的左字符，说明中间可以连接
新的最大长度可能来自：左子区间最大值、右子区间最大值、或跨越中点的连接部分

算法步骤：

构建线段树，初始化每个节点的状态信息
对每个查询进行单点更新
更新后查询根节点获取全局最长重复子串长度

时间复杂度为 O(n + k log n)，其中构建线段树 O(n)，每次查询更新 O(log n)。

代码实现

class Solution {
private:
    struct Node {
        char leftChar, rightChar;
        int leftLen, rightLen, maxLen;
        Node() : leftChar(0), rightChar(0), leftLen(0), rightLen(0), maxLen(0) {}
    };
    
    vector<Node> tree;
    string s;
    int n;
    
    void build(int node, int start, int end) {
        if (start == end) {
            tree[node].leftChar = tree[node].rightChar = s[start];
            tree[node].leftLen = tree[node].rightLen = tree[node].maxLen = 1;
        } else {
            int mid = (start + end) / 2;
            build(2*node, start, mid);
            build(2*node+1, mid+1, end);
            merge(node, start, end);
        }
    }
    
    void merge(int node, int start, int end) {
        int leftChild = 2*node, rightChild = 2*node+1;
        int mid = (start + end) / 2;
        
        tree[node].leftChar = tree[leftChild].leftChar;
        tree[node].rightChar = tree[rightChild].rightChar;
        tree[node].maxLen = max(tree[leftChild].maxLen, tree[rightChild].maxLen);
        
        tree[node].leftLen = tree[leftChild].leftLen;
        if (tree[leftChild].leftLen == mid - start + 1 && 
            tree[leftChild].rightChar == tree[rightChild].leftChar) {
            tree[node].leftLen += tree[rightChild].leftLen;
        }
        
        tree[node].rightLen = tree[rightChild].rightLen;
        if (tree[rightChild].rightLen == end - mid && 
            tree[leftChild].rightChar == tree[rightChild].leftChar) {
            tree[node].rightLen += tree[leftChild].rightLen;
        }
        
        if (tree[leftChild].rightChar == tree[rightChild].leftChar) {
            tree[node].maxLen = max(tree[node].maxLen, 
                                  tree[leftChild].rightLen + tree[rightChild].leftLen);
        }
    }
    
    void update(int node, int start, int end, int idx, char val) {
        if (start == end) {
            s[idx] = val;
            tree[node].leftChar = tree[node].rightChar = val;
        } else {
            int mid = (start + end) / 2;
            if (idx <= mid) {
                update(2*node, start, mid, idx, val);
            } else {
                update(2*node+1, mid+1, end, idx, val);
            }
            merge(node, start, end);
        }
    }
    
public:
    vector<int> longestRepeating(string s, string queryCharacters, vector<int>& queryIndices) {
        this->s = s;
        this->n = s.length();
        tree.resize(4 * n);
        
        build(1, 0, n-1);
        
        vector<int> result;
        for (int i = 0; i < queryCharacters.length(); i++) {
            update(1, 0, n-1, queryIndices[i], queryCharacters[i]);
            result.push_back(tree[1].maxLen);
        }
        
        return result;
    }
};

class Solution:
    def longestRepeating(self, s: str, queryCharacters: str, queryIndices: List[int]) -> List[int]:
        class Node:
            def __init__(self):
                self.leftChar = self.rightChar = ''
                self.leftLen = self.rightLen = self.maxLen = 0
        
        n = len(s)
        tree = [Node() for _ in range(4 * n)]
        s = list(s)
        
        def build(node, start, end):
            if start == end:
                tree[node].leftChar = tree[node].rightChar = s[start]
                tree[node].leftLen = tree[node].rightLen = tree[node].maxLen = 1
            else:
                mid = (start + end) // 2
                build(2*node, start, mid)
                build(2*node+1, mid+1, end)
                merge(node, start, end)
        
        def merge(node, start, end):
            leftChild, rightChild = 2*node, 2*node+1
            mid = (start + end) // 2
            
            tree[node].leftChar = tree[leftChild].leftChar
            tree[node].rightChar = tree[rightChild].rightChar
            tree[node].maxLen = max(tree[leftChild].maxLen, tree[rightChild].maxLen)
            
            tree[node].leftLen = tree[leftChild].leftLen
            if (tree[leftChild].leftLen == mid - start + 1 and 
                tree[leftChild].rightChar == tree[rightChild].leftChar):
                tree[node].leftLen += tree[rightChild].leftLen
            
            tree[node].rightLen = tree[rightChild].rightLen
            if (tree[rightChild].rightLen == end - mid and 
                tree[leftChild].rightChar == tree[rightChild].leftChar):
                tree[node].rightLen += tree[leftChild].rightLen
            
            if tree[leftChild].rightChar == tree[rightChild].leftChar:
                tree[node].maxLen = max(tree[node].maxLen, 
                                      tree[leftChild].rightLen + tree[rightChild].leftLen)
        
        def update(node, start, end, idx, val):
            if start == end:
                s[idx] = val
                tree[node].leftChar = tree[node].rightChar = val
            else:
                mid = (start + end) // 2
                if idx <= mid:
                    update(2*node, start, mid, idx, val)
                else:
                    update(2*node+1, mid+1, end, idx, val)
                merge(node, start, end)
        
        build(1, 0, n-1)
        
        result = []
        for i in range(len(queryCharacters)):
            update(1, 0, n-1, queryIndices[i], queryCharacters[i])
            result.append(tree[1].maxLen)
        
        return result

public class Solution {
    private class Node {
        public char leftChar, rightChar;
        public int leftLen, rightLen, maxLen;
        
        public Node() {
            leftChar = rightChar = '\0';
            leftLen = rightLen = maxLen = 0;
        }
    }
    
    private Node[] tree;
    private char[] s;
    private int n;
    
    private void Build(int node, int start, int end) {
        if (start == end) {
            tree[node].leftChar = tree[node].rightChar = s[start];
            tree[node].leftLen = tree[node].rightLen = tree[node].maxLen = 1;
        } else {
            int mid = (start + end) / 2;
            Build(2 * node, start, mid);
            Build(2 * node + 1, mid + 1, end);
            Merge(node, start, end);
        }
    }
    
    private void Merge(int node, int start, int end) {
        int leftChild = 2 * node, rightChild = 2 * node + 1;
        int mid = (start + end) / 2;
        
        tree[node].leftChar = tree[leftChild].leftChar;
        tree[node].rightChar = tree[rightChild].rightChar;
        tree[node].maxLen = Math.Max(tree[leftChild].maxLen, tree[rightChild].maxLen);
        
        tree[node].leftLen = tree[leftChild].leftLen;
        if (tree[leftChild].leftLen == mid - start + 1 && 
            tree[leftChild].rightChar == tree[rightChild].leftChar) {
            tree[node].leftLen += tree[rightChild].leftLen;
        }
        
        tree[node].rightLen = tree[rightChild].rightLen;
        if (tree[rightChild].rightLen == end - mid && 
            tree[leftChild].rightChar == tree[rightChild].leftChar) {
            tree[node].rightLen += tree[leftChild].rightLen;
        }
        
        if (tree[leftChild].rightChar == tree[rightChild].leftChar) {
            tree[node].maxLen = Math.Max(tree[node].maxLen, 
                                        tree[leftChild].rightLen + tree[rightChild].leftLen);
        }
    }
    
    private void Update(int node, int start, int end, int idx, char val) {
        if (start == end) {
            s[idx] = val;
            tree[node].leftChar = tree[node].rightChar = val;
        } else {
            int mid = (start + end) / 2;
            if (idx <= mid) {
                Update(2 * node, start, mid, idx, val);
            } else {
                Update(2 * node + 1, mid + 1, end, idx, val);
            }
            Merge(node, start, end);
        }
    }
    
    public int[] LongestRepeating(string s, string queryCharacters, int[] queryIndices) {
        this.s = s.ToCharArray();
        this.n = s.Length;
        tree = new Node[4 * n];
        for (int i = 0; i < tree.Length; i++) {
            tree[i] = new Node();
        }
        
        Build(1, 0, n - 1);
        
        int[] result = new int[queryCharacters.Length];
        for (int i = 0; i < queryCharacters.Length; i++) {
            Update(1, 0, n - 1, queryIndices[i], queryCharacters[i]);
            result[i] = tree[1].maxLen;
        }
        
        return result;
    }
}

var longestRepeating = function(s, queryCharacters, queryIndices) {
    const n = s.length;
    const k = queryCharacters.length;
    const result = [];
    const chars = s.split('');
    
    // Track segments of consecutive same characters
    const segments = new Set();
    
    // Helper function to find segment boundaries
    function findSegment(index) {
        let left = index;
        let right = index;
        
        while (left > 0 && chars[left - 1] === chars[index]) {
            left--;
        }
        while (right < n - 1 && chars[right + 1] === chars[index]) {
            right++;
        }
        
        return { left, right, length: right - left + 1 };
    }
    
    // Initialize segments
    let i = 0;
    while (i < n) {
        let j = i;
        while (j < n && chars[j] === chars[i]) {
            j++;
        }
        segments.add(JSON.stringify({ left: i, right: j - 1, length: j - i }));
        i = j;
    }
    
    function getMaxLength() {
        let maxLen = 0;
        for (const segStr of segments) {
            const seg = JSON.parse(segStr);
            maxLen = Math.max(maxLen, seg.length);
        }
        return maxLen;
    }
    
    for (let q = 0; q < k; q++) {
        const index = queryIndices[q];
        const newChar = queryCharacters[q];
        
        if (chars[index] === newChar) {
            result.push(getMaxLength());
            continue;
        }
        
        // Remove old segments that are affected
        const oldSegmentsToRemove = [];
        for (const segStr of segments) {
            const seg = JSON.parse(segStr);
            if (seg.left <= index && index <= seg.right) {
                oldSegmentsToRemove.push(segStr);
            }
        }
        
        for (const segStr of oldSegmentsToRemove) {
            segments.delete(segStr);
        }
        
        chars[index] = newChar;
        
        // Find new segments after the change
        const newSegments = [];
        
        // Check segments that might be affected
        let left = index;
        let right = index;
        
        // Extend left
        while (left > 0 && chars[left - 1] === newChar) {
            left--;
        }
        
        // Extend right
        while (right < n - 1 && chars[right + 1] === newChar) {
            right++;
        }
        
        // Add the new merged segment
        segments.add(JSON.stringify({ left, right, length: right - left + 1 }));
        
        // Handle remaining parts of the old segment if it was split
        if (oldSegmentsToRemove.length > 0) {
            const oldSeg = JSON.parse(oldSegmentsToRemove[0]);
            
            // Left part
            if (oldSeg.left < left) {
                let leftEnd = left - 1;
                while (leftEnd >= oldSeg.left && chars[leftEnd] === chars[oldSeg.left]) {
                    leftEnd++;
                }
                leftEnd--;
                if (leftEnd >= oldSeg.left) {
                    segments.add(JSON.stringify({ 
                        left: oldSeg.left, 
                        right: leftEnd, 
                        length: leftEnd - oldSeg.left + 1 
                    }));
                }
            }
            
            // Right part
            if (oldSeg.right > right) {
                let rightStart = right + 1;
                while (rightStart <= oldSeg.right && chars[rightStart] === chars[oldSeg.right]) {
                    rightStart--;
                }
                rightStart++;
                if (rightStart <= oldSeg.right) {
                    segments.add(JSON.stringify({ 
                        left: rightStart, 
                        right: oldSeg.right, 
                        length: oldSeg.right - rightStart + 1 
                    }));
                }
            }
        }
        
        result.push(getMaxLength());
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

指标	复杂度
时间	-
空间	-

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目