Medium

题目描述

给你一个长度为 n 的字符串 s 和一个整数数组 order，其中 order 是范围 [0, n - 1] 内数字的一个排列。

从时间 t = 0 开始，在每个时间步将字符串 s 中索引为 order[t] 的字符替换为 ‘*’。

如果一个子字符串包含至少一个 ‘*’，则该子字符串是有效的。

如果有效子字符串的总数大于或等于 k，则字符串是活跃的。

返回字符串 s 变为活跃的最小时间 t。如果不可能，返回 -1。

示例 1：

输入: s = "abc", order = [1,0,2], k = 2
输出: 0
解释: 
t=0时，order[0]=1，字符串变为"a*c"
有效子字符串: "*", "a*", "*c", "a*c"，共4个
4 >= 2，所以字符串在t=0时变为活跃。

示例 2：

输入: s = "cat", order = [0,2,1], k = 6
输出: 2
解释:
t=0: "*at"，有效子字符串3个
t=1: "*a*"，有效子字符串5个  
t=2: "***"，所有子字符串都有效，共6个
字符串在t=2时变为活跃。

示例 3：

输入: s = "xy", order = [0,1], k = 4
输出: -1
解释: 即使所有字符都替换后，也无法获得4个有效子字符串。

约束条件：

  • 1 <= n == s.length <= 10^5
  • order.length == n
  • 0 <= order[i] <= n - 1
  • s 由小写英文字母组成
  • order 是从 0 到 n-1 的整数排列
  • 1 <= k <= 10^9

解题思路

这是一道二分搜索题目。关键思路如下：

核心观察： 有效子字符串数量随着时间t单调递增，因此可以使用二分搜索找到最小的满足条件的时间。

计算有效子字符串数量： 对于给定时间t，我们知道前t+1个位置会被替换为’*’。计算有效子字符串的关键是：

  • 总子字符串数量为 n*(n+1)/2
  • 无效子字符串是那些完全不包含’*‘的子字符串
  • 无效子字符串只能来自连续的非’*‘字符段

算法步骤：

  1. 二分搜索时间t的范围[0, n-1]
  2. 对于每个t，标记前t+1个order位置为’*’
  3. 找出所有连续的非’*‘字符段
  4. 对于长度为L的连续段，其子字符串数量为L*(L+1)/2
  5. 有效子字符串数量 = 总数 - 所有连续非’*‘段的子字符串数量
  6. 检查是否 >= k

时间优化： 由于k可能很大(10^9)，当所有字符都替换为’*‘后仍然不够时，直接返回-1。

代码实现

class Solution {
public:
    int minTime(string s, vector<int>& order, int k) {
        int n = s.length();
        long long total = (long long)n * (n + 1) / 2;
        if (total < k) return -1;
        
        int left = 0, right = n - 1;
        int result = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            vector<bool> isReplaced(n, false);
            for (int i = 0; i <= mid; i++) {
                isReplaced[order[i]] = true;
            }
            
            long long invalid = 0;
            int i = 0;
            while (i < n) {
                if (!isReplaced[i]) {
                    int len = 0;
                    while (i < n && !isReplaced[i]) {
                        len++;
                        i++;
                    }
                    invalid += (long long)len * (len + 1) / 2;
                } else {
                    i++;
                }
            }
            
            long long valid = total - invalid;
            if (valid >= k) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return result;
    }
};

class Solution:
    def minTime(self, s: str, order: List[int], k: int) -> int:
        n = len(s)
        total = n * (n + 1) // 2
        if total < k:
            return -1
        
        left, right = 0, n - 1
        result = -1
        
        while left <= right:
            mid = (left + right) // 2
            
            is_replaced = [False] * n
            for i in range(mid + 1):
                is_replaced[order[i]] = True
            
            invalid = 0
            i = 0
            while i < n:
                if not is_replaced[i]:
                    length = 0
                    while i < n and not is_replaced[i]:
                        length += 1
                        i += 1
                    invalid += length * (length + 1) // 2
                else:
                    i += 1
            
            valid = total - invalid
            if valid >= k:
                result = mid
                right = mid - 1
            else:
                left = mid + 1
        
        return result

public class Solution {
    public int MinTime(string s, int[] order, int k) {
        int n = s.Length;
        long total = (long)n * (n + 1) / 2;
        if (total < k) return -1;
        
        int left = 0, right = n - 1;
        int result = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            bool[] isReplaced = new bool[n];
            for (int i = 0; i <= mid; i++) {
                isReplaced[order[i]] = true;
            }
            
            long invalid = 0;
            int i = 0;
            while (i < n) {
                if (!isReplaced[i]) {
                    int len = 0;
                    while (i < n && !isReplaced[i]) {
                        len++;
                        i++;
                    }
                    invalid += (long)len * (len + 1) / 2;
                } else {
                    i++;
                }
            }
            
            long valid = total - invalid;
            if (valid >= k) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return result;
    }
}

var minTime = function(s, order, k) {
    const n = s.length;
    const total = Math.floor(n * (n + 1) / 2);
    if (total < k) return -1;
    
    let left = 0, right = n - 1;
    let result = -1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        const isReplaced = new Array(n).fill(false);
        for (let i = 0; i <= mid; i++) {
            isReplaced[order[i]] = true;
        }
        
        let invalid = 0;
        let i = 0;
        while (i < n) {
            if (!isReplaced[i]) {
                let len = 0;
                while (i < n && !isReplaced[i]) {
                    len++;
                    i++;
                }
                invalid += Math.floor(len * (len + 1) / 2);
            } else {
                i++;
            }
        }
        
        const valid = total - invalid;
        if (valid >= k) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n log n)，其中 n 是字符串长度。二分搜索进行 O(log n) 次，每次需要 O(n) 时间计算有效子字符串数量
空间复杂度O(n)，需要额外的布尔数组来标记哪些位置被替换