算法基础算法

贪心：构造性问题

字数统计: 4.9k字   |   阅读时长: 22分
, , , ,

摘要: 基于贪心的构造问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

构造是算法中广泛使用的一类技巧。其中贪心地构造是比较考验灵感的问题，没有定式化的方法论。本文整理了一些这类问题，共 11 题。

1354. 多次求和构造目标数组

本题的算法是用逆向思维进行模拟，参考题解：逆向思维。

1558. 得到目标数组的最少函数调用次数

本题的算法是用逆向思维进行模拟，参考题解：逆向思维。

1253. 重构 2 行二进制矩阵

给你一个 2 行 n 列的二进制数组：

  • 矩阵是一个二进制矩阵，这意味着矩阵中的每个元素不是 0 就是 1。
  • 第 0 行的元素之和为 upper。
  • 第 1 行的元素之和为 lower。
  • 第 i 列（从 0 开始编号）的元素之和为 colsum[i]，colsum 是一个长度为 n 的整数数组。

你需要利用 upper，lower 和 colsum 来重构这个矩阵，并以二维整数数组的形式返回它。

如果有多个不同的答案，那么任意一个都可以通过本题。

如果不存在符合要求的答案，就请返回一个空的二维数组。

示例 1：
输入：upper = 2, lower = 1, colsum = [1,1,1]
输出：[[1,1,0],[0,0,1]]
解释：[[1,0,1],[0,1,0]] 和 [[0,1,1],[1,0,0]] 也是正确答案。

示例 2：
输入：upper = 2, lower = 3, colsum = [2,2,1,1]
输出：[]

示例 3：
输入：upper = 5, lower = 5, colsum = [2,1,2,0,1,0,1,2,0,1]
输出：[[1,1,1,0,1,0,0,1,0,0],[1,0,1,0,0,0,1,1,0,1]]

提示：

1
2
3
1 <= colsum.length <= 1e5
0 <= upper, lower <= colsum.length
0 <= colsum[i] <= 2

算法：贪心、模拟

枚举列编号 $j = 0, 1, \cdots, m-1$，贪心地构造矩阵的第 $j$ 列 $result[0][j]、result[0][j]$。

$colsum[j]$ 为 0 或 2 是比较简单的情况，此时第 $j$ 列只有一种构造方法：

  • 若 $colsum[j]$ 为 0，则 $result[0][j]$ 和 $result[1][j]$ 均为 0。
  • 若 $colsum[j]$ 为 2，则 $result[0][j]$ 和 $result[1][j]$ 均为 1。同时 upper 和 lower 均减 1。

$colsum[j]$ 为 1 是比较复杂的情况，还需要分类讨论：

  • $lower$ 和 $upper$ 均为 0：则无法构造，返回空数组。
  • $lower > upper$：则优先把下面填上 1，即 $result[1][j]$ 填 1，$result[0][j]$ 填 0。
  • $lower \leq upper$：则优先把上面填上 1，即 $result[0][j]$ 填 1，$result[1][j]$ 填 0。

上面的填写策略中，$lower$ 和 $upper$ 谁大就相应地把对应的行填 1，原因在于这样可以在后续的构造中应对更多的 $colsum$ 为 2 的列。

可以通过决策包容性证明上述贪心策略的正确性，即做出局部最优策略之后，在问题状态空间中的可达集合包含了做出其它决策的可达集合。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
        int m = colsum.size();
        vector<vector<int>> result(2, vector<int>(m, -1));
        for(int j = 0; j < m; ++j)
        {
            if(colsum[j] == 0)
            {
                result[0][j] = 0;
                result[1][j] = 0;
            }
            else if(colsum[j] == 2)
            {
                if(upper == 0 || lower == 0)
                    return {};
                result[0][j] = 1;
                result[1][j] = 1;
                --upper;
                --lower;
            }
            else
            {
                if(lower == 0 && upper == 0)
                    return {};
                if(lower > upper)
                {
                    --lower;
                    result[0][j] = 0;
                    result[1][j] = 1;
                }
                else
                {
                    --upper;
                    result[0][j] = 1;
                    result[1][j] = 0;
                }
            }
        }
        if(upper > 0 || lower > 0)
            return {};
        return result;
    }
};

1605. 给定行和列的和求可行矩阵

给你两个非负整数数组 rowSum 和 colSum ，其中 rowSum[i] 是二维矩阵中第 i 行元素的和， colSum[j] 是第 j 列元素的和。换言之你不知道矩阵里的每个元素，但是你知道每一行和每一列的和。

请找到大小为 rowSum.length x colSum.length 的任意 非负整数 矩阵，且该矩阵满足 rowSum 和 colSum 的要求。

请你返回任意一个满足题目要求的二维矩阵，题目保证存在 至少一个 可行矩阵。

示例 1：
输入：rowSum = [3,8], colSum = [4,7]
输出：[[3,0],
[1,7]]
解释：
第 0 行：3 + 0 = 3 == rowSum[0]
第 1 行：1 + 7 = 8 == rowSum[1]
第 0 列：3 + 1 = 4 == colSum[0]
第 1 列：0 + 7 = 7 == colSum[1]
行和列的和都满足题目要求，且所有矩阵元素都是非负的。
另一个可行的矩阵为：[[1,2],
[3,5]]

示例 2：
输入：rowSum = [5,7,10], colSum = [8,6,8]
输出：[[0,5,0],
[6,1,0],
[2,0,8]]

示例 3：
输入：rowSum = [14,9], colSum = [6,9,8]
输出：[[0,9,5],
[6,0,3]]

示例 4：
输入：rowSum = [1,0], colSum = [1]
输出：[[1],
[0]]

示例 5：
输入：rowSum = [0], colSum = [0]
输出：[[0]]

提示：

1
2
3
1 <= rowSum.length, colSum.length <= 500
0 <= rowSum[i], colSum[i] <= 1e8
sum(rowSum) == sum(colSum)

算法：贪心

枚举 (i, j)，置 result[i][j] = min(rowSum[i], colSum[j])，更新 rowSum[i] 和 colSum[j]。

证明方法，分析第一行在构造完成后该行是否可以将 rowSum[i] 刚好用完，同时 colSum[0..m] 大于等于 0。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<vector<int>> restoreMatrix(vector<int>& rowSum, vector<int>& colSum) {
        int n = rowSum.size(), m = colSum.size();
        vector<vector<int>> result(n, vector<int>(m, 0));
        for(int i = 0; i < n; ++i)
        {
            for(int j = 0; j < m; ++j)
            {
                int x = rowSum[i];
                int y = colSum[j];
                int z = min(x, y);
                result[i][j] = z;
                rowSum[i] -= z;
                colSum[j] -= z;
            }
        }
        return result;
    }
};

1405. 最长快乐字符串

如果字符串中不含有任何 ‘aaa’，’bbb’ 或 ‘ccc’ 这样的字符串作为子串，那么该字符串就是一个「快乐字符串」。

给你三个整数 a，b ，c，请你返回 任意一个 满足下列全部条件的字符串 s：

  • s 是一个尽可能长的快乐字符串。
  • s 中 最多 有a 个字母 ‘a’、b 个字母 ‘b’、c 个字母 ‘c’ 。
  • s 中只含有 ‘a’、’b’ 、’c’ 三种字母。

如果不存在这样的字符串 s ，请返回一个空字符串 “”。

示例 1：
输入：a = 1, b = 1, c = 7
输出：”ccaccbcc”
解释：”ccbccacc” 也是一种正确答案。

示例 2：
输入：a = 2, b = 2, c = 1
输出：”aabbc”

示例 3：
输入：a = 7, b = 1, c = 0
输出：”aabaa”
解释：这是该测试用例的唯一正确答案。

提示：

1
2
0 <= a, b, c <= 100
a + b + c > 0

算法：贪心

一个字符一个字符地构造字符串，在构造当前字符时，考虑 ‘a’，’b’，’c’ 三种字符剩余的额度，记其为 a, b, c，不妨设 $a \leq b \leq c$，分类讨论不同情况的构造策略。

$b$ 或 $c$ 等于 0 的情况比较简单，先单独讨论：

  • 如果 $c = 0$，则三种字符都没额度了，此时的构造就到头了，直接返回。
  • 如果 $b = 0$，那么后续只能填字符 ‘c’，基于所剩额度尽可能多填即可，最多构造 3 个。根据后续的构造策略，前面的字符不是 ‘b’ 就是 ‘a’，因此填 3 个 ‘c’ 时不用考虑与前面的 ‘c’ 连成 4 个以上的情况。

现在 $b, c$ 均大于 $0$，$a$ 有可能等于零。下面继续分类讨论：

  • 如果 $a = b = c$，那么它们肯定都大于 0，于是构造一个 “cba” 即可，这里把 ‘a’ 放最后，可以应对前面 $b = 0$ 时尽可能多填 ‘c’ 的情况。
  • 如果 $a < b = c$，那么构造一个 “cb”。
  • 如果 $a = b < c$，那么构造一个 “ccb”。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
struct Char
{
    char ch;
    int cnt;
    Char(char ch, int cnt):ch(ch),cnt(cnt){}
};

struct Cmp
{
    bool operator()(const Char& c1, const Char& c2)
    {
        if(c1.cnt == c2.cnt)
            return c1.ch < c2.ch;
        return c1.cnt < c2.cnt;
    }
};

class Solution {
public:
    string longestDiverseString(int a, int b, int c) {
        string ans;
        Char A('a', a);
        Char B('b', b);
        Char C('c', c);
        vector<Char> sorted = {A, B, C};
        solve(sorted, ans);
        return ans;
    }

private:
    void solve(vector<Char>& chars, string& s)
    {
        // c >= b >= a
        sort(chars.begin(), chars.end(), Cmp());
        if(chars[2].cnt == 0)
            return;
        if(chars[1].cnt == 0)
        {
            for(int i = 0; i < min(chars[2].cnt, 2); ++i)
                s += chars[2].ch;
            return;
        }
        if(chars[1].cnt == chars[2].cnt && chars[0].cnt == chars[1].cnt)
        {
            for(int i = 0; i < chars[0].cnt; ++i)
                s += "cba";
            return;
        }
        // 一定有一个小于号
        // chars[2] == chars[1] > chars[0]
        if(chars[1].cnt == chars[2].cnt)
        {
            s += chars[2].ch;
            s += chars[1].ch;
            --chars[2].cnt;
            --chars[1].cnt;
            solve(chars, s);
            return;
        }
        // chars[2] > chars[1] >= chars[0]
        s += chars[2].ch;
        s += chars[2].ch;
        s += chars[1].ch;
        --chars[2].cnt;
        --chars[2].cnt;
        --chars[1].cnt;
        solve(chars, s);
    }
};

1046. 最后一块石头的重量

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

  • 如果 x == y，那么两块石头都会被完全粉碎；
  • 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

提示：

1
2
1 <= stones.length <= 30
1 <= stones[i] <= 1000

示例：
输入：[2,7,4,1,8,1]
输出：1
解释：
先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]，
再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]，
接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]，
最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。

算法：模拟、平衡树

由于每次都要选出两个最重的石头，因此需要用平衡树或堆来维护若干个石头。

然后按照流程模拟即可，每次从平衡树中弹出两个最大值 $x \leq y$，若 $x \neq y$ 则将 $y - x$ 压入。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        multiset<int> setting(stones.begin(), stones.end());
        while(setting.size() > 1)
        {
            int y = *setting.rbegin();
            setting.erase(--setting.end());
            int x = *setting.rbegin();
            setting.erase(--setting.end());
            if(x < y)
                setting.insert(y - x);
        }
        return *setting.begin();
    }
};

995. K 连续位的最小翻转次数

给定一个二进制数组 nums 和一个整数 k 。

k位翻转 就是从 nums 中选择一个长度为 k 的 子数组 ，同时把子数组中的每一个 0 都改成 1 ，把子数组中的每一个 1 都改成 0 。

返回数组中不存在 0 所需的最小 k位翻转 次数。如果不可能，则返回 -1 。

子数组 是数组的 连续 部分。

提示：

1
2
1 <= nums.length <= 1e5
1 <= k <= nums.length

示例 1：
输入：nums = [0,1,0], K = 1
输出：2
解释：先翻转 A[0]，然后翻转 A[2]。

示例 2：
输入：nums = [1,1,0], K = 2
输出：-1
解释：无论我们怎样翻转大小为 2 的子数组，我们都不能使数组变为 [1,1,1]。

示例 3：
输入：nums = [0,0,0,1,0,1,1,0], K = 3
输出：3
解释：
翻转 A[0],A[1],A[2]: A变成 [1,1,1,1,0,1,1,0]
翻转 A[4],A[5],A[6]: A变成 [1,1,1,1,1,0,0,0]
翻转 A[5],A[6],A[7]: A变成 [1,1,1,1,1,1,1,1]

算法：贪心

贪心思路：如果最左边的元素是 0，那么我们一定要翻转从位置 0 开始的子数组。类似的，如果最左边的元素是 1，我们不应该翻转从位置 0 开始的子数组。

维护贪心的算法：只维护区间端点信息。

每次翻转的区间的左右端点位置为两种事件：左事件和右事件。用一个变量 flip 记录当前点的事件次数，每当发生翻转时，++flip 并记录右端点的位置，当枚举到那个位置的时候，把 flip 减 1.

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int minKBitFlips(vector<int>& A, int K) {
        int n = A.size();
        if(n < K)
            return -1;
        int ans = 0;
        int flip = 0;
        vector<int> events(n, 0);
        for(int l = 0; l < n; ++l)
        {
            if((A[l] ^ flip) == 0)
            {
                if(l + K - 1 >= n)
                    return -1;
                flip ^= 1;
                events[l + K - 1] = 1;
                ++ans;
            }
            flip ^= events[l];
        }
        return ans;
    }
};

984. 不含 AAA 或 BBB 的字符串

给定两个整数 a 和 b ，返回 任意 字符串 s ，要求满足：

  • s 的长度为 a + b，且正好包含 a 个 ‘a’ 字母与 b 个 ‘b’ 字母；
  • 子串 ‘aaa’ 没有出现在 s 中；
  • 子串 ‘bbb’ 没有出现在 s 中。

提示：

1
2
0 <= a, b <= 100
对于给定的 a 和 b，保证存在满足要求的 s

示例 1：
输入：a = 1, b = 2
输出：”abb”
解释：”abb”, “bab” 和 “bba” 都是正确答案。

示例 2：
输入：a = 4, b = 1
输出：”aabaa”

算法：贪心

在构造过程中，维护 delta = A - B。

  • =0 : 直接 ab。
  • >0 : 先 aab 再 ab。
  • <0 : 先 bba 再 ba。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution
{
public:
    string strWithout3a3b(int A, int B)
    {
        string result = "";
        int delta = A - B;
        if(delta == 0)
        {
            // A == B
            for(int i = 0; i < (A + B) / 2; ++i)
                result += "ab";
        }
        else if(delta > 0)
        {
            // A > B
            int num_aa = delta - 1;
            if(num_aa > B)
            {
                for(int i = 0; i < B; ++i)
                    result += "aab";
                result += "aa";
            }
            else
            {
                for(int i = 0; i < num_aa; ++i)
                    result += "aab";
                for(int i = 0; i < B - num_aa; ++i)
                    result += "ab";
                result += "a";
            }
        }
        else
        {
            // A < B
            int num_bb = - delta - 1;
            if(num_bb > A)
            {
                for(int i = 0; i < A; ++i)
                    result += "bba";
                result += "bb";
            }
            else
            {
                for(int i = 0; i < num_bb; ++i)
                    result += "bba";
                for(int i = 0; i < A - num_bb; ++i)
                    result += "ba";
                result += "b";
            }
        }
        return result;
    }
};

484. 寻找排列

由范围 [1,n] 内所有整数组成的 n 个整数的排列 perm 可以表示为长度为 n - 1 的字符串 s ，其中:

  • 如果 perm[i] < perm[i + 1] ，那么 s[i] == ‘I’；
  • 如果 perm[i] > perm[i + 1] ，那么 s[i] == ‘D’ 。

给
提示：

1
2
1 <= s.length <= 1e5
s[i] 只会包含字符 'D' 和 'I'。

定一个字符串 s ，重构字典序上最小的排列 perm 并返回它。

示例 1：
输入： s = “I”
输出： [1,2]
解释： [1,2] 是唯一合法的可以生成秘密签名 “I” 的特定串，数字 1 和 2 构成递增关系。

示例 2：
输入： s = “DI”
输出： [2,1,3]
解释： [2,1,3] 和 [3,1,2] 可以生成秘密签名 “DI”，
但是由于我们要找字典序最小的排列，因此你需要输出 [2,1,3]。

算法：贪心

当前数字是 cur，枚举到 s[i]：

  • 若为 D，则将 --cur 加入答案。
  • 若为 I，则先找到此前已经插入的数字的最大值 maxx，如果不考虑后续的 D，则该位置应该插入 maxx + 1，但是后面可能有跟着的 D，因此需要提前计算好提前量，记 net_nd[i] := 从 i + 1 开始连续的 D 的个数，则该点应该插入 maxx + 1 + net_nd[i]。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
public:
    vector<int> findPermutation(string s) {
        int n = s.size();
        // 1..n+1
        vector<int> net_nd(n, 0); // 从该点往后的连续 D 个数
        int i = 0;
        while(i < n)
        {
            const char &ch = s[i];
            if(ch == 'I')
            {
                net_nd[i] = 0;
                ++i;
                continue;
            }
            int j = i + 1;
            while(j < n && s[j] == 'D')
                ++j;
            int t = j - i;
            for(int k = 0; k < j - i; ++k)
                net_nd[i + k] = t--;
            i = j;
        }
        int cur = 0;
        vector<int> result;
        if(net_nd[0] == 0)
            result.push_back(++cur);
        else
        {
            result.push_back(cur + net_nd[0] + 1);
            cur += net_nd[0] + 1;
        }
        int maxx = cur;
        for(int i = 0; i < n; ++i)
        {
            if(s[i] == 'D')
            {
                result.push_back(--cur);
            }
            else
            {
                if(i < n - 1)
                {
                    result.push_back(maxx + 1 + net_nd[i + 1]);
                    maxx += 1 + net_nd[i + 1];
                }
                else
                    result.push_back(++maxx);
                cur = maxx;
            }
        }
        return result;
    }
};

1144. 递减元素使数组呈锯齿状

给你一个整数数组 nums，每次 操作 会从中选择一个元素并 将该元素的值减少 1。

如果符合下列情况之一，则数组 A 就是 锯齿数组：

  • 每个偶数索引对应的元素都大于相邻的元素，即 A[0] > A[1] < A[2] > A[3] < A[4] > …
  • 或者，每个奇数索引对应的元素都大于相邻的元素，即 A[0] < A[1] > A[2] < A[3] > A[4] < …

返回将数组 nums 转换为锯齿数组所需的最小操作次数。

提示：

1
2
1 <= nums.length <= 1000
1 <= nums[i] <= 1000

示例 1：
输入：nums = [1,2,3]
输出：2
解释：我们可以把 2 递减到 0，或把 3 递减到 1。

示例 2：
输入：nums = [9,6,1,6,2]
输出：4

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int movesToMakeZigzag(vector<int>& nums) {
        int n = nums.size();
        if(n <= 2) return 0;
        int result1 = 0; // 使得奇数位置元素大于相邻的答案
        int result2 = 0; // 使得偶数位置元素大于相邻的答案
        for(int i = 0; i < n; ++i)
        {
            if(i & 1)
            {
                int tmp = 0;
                tmp = max(tmp, nums[i] - nums[i - 1] + 1);
                if(i != n - 1)
                    tmp = max(tmp, nums[i] - nums[i + 1] + 1);
                result1 += tmp;
            }
            else
            {
                int tmp = 0;
                if(i != n - 1)
                    tmp = max(tmp, nums[i] - nums[i + 1] + 1);
                if(i != 0)
                    tmp = max(tmp, nums[i] - nums[i - 1] + 1);
                result2 += tmp;
            }
        }
        return min(result1, result2);
    }
};

1540. K 次操作转变字符串

给你两个字符串 s 和 t ，你的目标是在 k 次操作以内把字符串 s 转变成 t 。

在第 i 次操作时（1 <= i <= k），你可以选择进行如下操作：

  • 选择字符串 s 中满足 1 <= j <= s.length 且之前未被选过的任意下标 j （下标从 1 开始），并将此位置的字符切换 i 次。
  • 不进行任何操作。

切换 1 个字符的意思是用字母表中该字母的下一个字母替换它（字母表环状接起来，所以 ‘z’ 切换后会变成 ‘a’）。第 i 次操作意味着该字符应切换 i 次

请记住任意一个下标 j 最多只能被操作 1 次。

如果在不超过 k 次操作内可以把字符串 s 转变成 t ，那么请你返回 true ，否则请你返回 false 。

提示：

1
2
3
1 <= s.length, t.length <= 1e5
0 <= k <= 1e9
s 和 t 只包含小写英文字母。

示例 1：
输入：s = “input”, t = “ouput”, k = 9
输出：true
解释：第 6 次操作时，我们将 ‘i’ 切换 6 次得到 ‘o’ 。第 7 次操作时，我们将 ‘n’ 切换 7 次得到 ‘u’ 。

示例 2：
输入：s = “abc”, t = “bcd”, k = 10
输出：false
解释：我们需要将每个字符切换 1 次才能得到 t 。我们可以在第 1 次操作时将 ‘a’ 切换成 ‘b’ ，但另外 2 个字母在剩余操作中无法再转变为 t 中对应字母。

示例 3：
输入：s = “aab”, t = “bbb”, k = 27
输出：true
解释：第 1 次操作时，我们将第一个 ‘a’ 切换 1 次得到 ‘b’ 。在第 27 次操作时，我们将第二个字母 ‘a’ 切换 27 次得到 ‘b’ 。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool canConvertString(string s, string t, int k) {
        int ns = s.size(), nt = t.size();
        if(ns != nt)
            return false;
        vector<int> cnts(26);
        for(int i = 0; i < ns; ++i)
            ++cnts[(t[i] + 26 - s[i]) % 26];
        for(int t = 0; t < 26; ++t)
        {
            if(t > 0 && cnts[t] > 0)
            {
                int r = (cnts[t] - 1) * 26 + t;
                if(r > k)
                    return false;
            }
        }
        return true;
    }
};
Share