You are given a string s of length n, an integer array order of length n which is a permutation of integers from $0$ to $n - 1$, and an integer k.

At each second t starting from $0$, the character at index order[t] in s is replaced with the character '*'.

A substring of s is considered valid if it contains at least one '*'.

The string s becomes active when the total number of valid substrings is greater than or equal to k.

Return the minimum time t at which s becomes active. If it is impossible for s to become active after all replacements, return $-1$.

Constraints:

• $1 \leq n ==$ s.length $\leq 10^5$

• order.length $== n$

• $0 \leq$ order[i] $\leq n - 1$

• s consists of lowercase English letters.

• order is a permutation of integers from $0$ to $n - 1$.

• $1 \leq k \leq 10^9$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.