跳转至

3639. 变为活跃状态的最小时间

题目描述

给你一个长度为 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 order[t] 修改后的 s 有效子字符串 计数 激活状态
(计数 >= k)
0 1 "a*c" "*", "a*", "*c", "a*c" 4 是

字符串 s 在 t = 0 时变为激活状态。因此，答案是 0。

示例 2:

输入: s = "cat", order = [0,2,1], k = 6

输出: 2

解释:

t order[t] 修改后的 s 有效子字符串 计数 激活状态
(计数 >= k)
0 0 "*at" "*", "*a", "*at" 3 否
1 2 "*a*" "*", "*a", "*a*", "a*", "*" 5 否
2 1 "***" 所有子字符串(包含 '*') 6 是

字符串 s 在 t = 2 时变为激活状态。因此，答案是 2。

示例 3:

输入: s = "xy", order = [0,1], k = 4

输出: -1

解释:

即使完成所有替换，也无法得到 k = 4 个有效子字符串。因此，答案是 -1。

 

提示:

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

解法

方法一

1


1


1


1

评论