解法：容斥 & 递推

我们把连续相同的字符视为一段。首先根据题意，原字符串中，每一段至少会保留一个字符。因此如果段数 $m$ 至少为 $k$，那么任何保留的方案都是合法的，答案就是 $\prod l$，其中 $l$ 是段长。

如果段数 $m$ 少于 $k$，我们可以扣掉总长不足 $k$ 的方案就是答案。维护 $f(i, j)$ 表示前 $i$ 段留下的总长是 $j$ 的方案数，枚举第 $i$ 段要留下多少字符，则递推方程为

$$
f(i, j) = \sum\limits_{t = 1}^{l_i} f(i - 1, j - t)
$$

用前缀和即可将复杂度优化成 $\mathcal{O}(k^2)$。答案就是 $\prod l - \sum\limits_{j = 1}^{k - 1} f(m, j)$。

参考代码（c++）

###cpp

class Solution {
public:
    int possibleStringCount(string word, int K) {
        int n = word.size();
        const int MOD = 1e9 + 7;

        vector<int> vec;
        for (int i = 0, j = 0; i < n; i++) {
            if (i == n - 1 || word[i] != word[i + 1]) {
                vec.push_back(i - j + 1);
                j = i + 1;
            }
        }

        int m = vec.size();
        long long ans = 1;
        for (int x : vec) ans = ans * x % MOD;
        if (m >= K) return ans;

        long long f[m + 1][K], g[m + 1][K];
        memset(f, 0, sizeof(f)); memset(g, 0, sizeof(g));
        f[0][0] = 1;
        for (int j = 0; j < K; j++) g[0][j] = 1;

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j < K; j++) {
                long long v = 0;
                int t = j - vec[i - 1] - 1;
                if (t >= 0) v = g[i - 1][t];
                f[i][j] = (g[i - 1][j - 1] - v + MOD) % MOD;
            }
            for (int j = 1; j < K; j++) g[i][j] = (g[i][j - 1] + f[i][j]) % MOD;
        }
        return (ans - g[m][K - 1] + MOD) % MOD;
    }
};

解法：枚举

假设 Alice 恰好犯错了一次，如果她在一段长度为 $l$ 的相同字符里犯错了，那么原字符串中，这一段字符可能会少 $1$ 个到 $(l - 1)$ 个。

因此枚举 Alice 在哪一段里犯错了，再加上 Alice 没犯错的情况，答案就是 $1 + \sum (l - 1)$。复杂度 $\mathcal{O}(n)$。

参考代码（c++）

###cpp

class Solution {
public:
    int possibleStringCount(string word) {
        int n = word.size();
        int ans = 1;
        for (int i = 0, j = 0; i < n; i++) {
            if (i == n - 1 || word[i] != word[i + 1]) {
                ans += i - j;
                j = i + 1;
            }
        }
        return ans;
    }
};

题解

通过二分查找第 $k$ 小的乘积 $p$，每次判定时枚举 nums1 中的数 $a$，通过二分再次判断 nums2 中有几个数 $b$ 满足 $ab \le p$。注意需要对 $a > 0$，$a < 0$ 和 $a = 0$ 三种情况分别讨论。复杂度 $\mathcal{O}(n\log n\log A)$。

代码

###c++

class Solution {
    vector<int> A, B;
    
    long long gao(long long lim) {
        long long ret = 0;
        for (long long x : A) {
            if (x > 0) {
                if (x * B[0] > lim) continue;
                int head = 0, tail = B.size() - 1;
                while (head < tail) {
                    int mid = (head + tail + 1) >> 1;
                    if (x * B[mid] <= lim) head = mid;
                    else tail = mid - 1;
                }
                ret += head + 1;
            } else if (x < 0) {
                if (x * B[B.size() - 1] > lim) continue;
                int head = 0, tail = B.size() - 1;
                while (head < tail) {
                    int mid = (head + tail) >> 1;
                    if (x * B[mid] <= lim) tail = mid;
                    else head = mid + 1;
                }
                ret += B.size() - head;
            } else if (lim >= 0) ret += B.size();
        }
        return ret;
    }
    
public:
    long long kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, long long k) {
        A = nums1; B = nums2;
        long long head = -1e11, tail = 1e11;
        while (head < tail) {
            long long mid = (head + tail) >> 1;
            long long x = gao(mid);
            if (x >= k) tail = mid;
            else head = mid + 1;
        }
        return head;
    }
};