1625-执行操作后字典序最小的字符串

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:32 2023-09-13 16:06:32 Updated    

给你一个字符串 s 以及两个整数 a 和 b 。其中，字符串 s 的长度为偶数，且仅由数字 0 到 9 组成。

你可以在 s 上按任意顺序多次执行下面两个操作之一：

  • 累加：将 a 加到 s 中所有下标为奇数的元素上（ 下标从 0 开始 ）。数字一旦超过 9 就会变成 0，如此循环往复。例如，s = "3456" 且 a = 5，则执行此操作后 s 变成 "3951"。
  • 轮转：将 s 向右轮转 b 位。例如，s = "3456" 且 b = 1，则执行此操作后 s 变成 "6345"。

请你返回在 s 上执行上述操作任意次后可以得到的 字典序最小 的字符串。

如果两个字符串长度相同，那么字符串 a 字典序比字符串 b 小可以这样定义：在 a 和 b 出现不同的第一个位置上，字符串 a
中的字符出现在字母表中的时间早于 b 中的对应字符。例如，"0158” 字典序比 "0190" 小，因为不同的第一个位置是在第三个字符，显然
'5' 出现在 '9' 之前。

示例 1：

**输入：** s = "5525", a = 9, b = 2
**输出：** "2050"
**解释：** 执行操作如下：
初态："5525"
轮转："2555"
累加："2454"
累加："2353"
轮转："5323"
累加："5222"
累加："5121"
轮转："2151"
累加："2050"​​​​​
无法获得字典序小于 "2050" 的字符串。

示例 2：

**输入：** s = "74", a = 5, b = 1
**输出：** "24"
**解释：** 执行操作如下：
初态："74"
轮转："47"
累加："42"
轮转："24"​​​​​
无法获得字典序小于 "24" 的字符串。

示例 3：

**输入：** s = "0011", a = 4, b = 2
**输出：** "0011"
**解释：** 无法获得字典序小于 "0011" 的字符串。

提示：

  • 2 <= s.length <= 100
  • s.length 是偶数
  • s 仅由数字 0 到 9 组成
  • 1 <= a <= 9
  • 1 <= b <= s.length - 1

方法一：枚举

思路与算法

题目有两种操作：

  1. 累加，将 s 的奇数位元素加上 a，超过 9 则回到 0 继续加。
  2. 轮转，将 s 向右轮转 b 位。

以上操作可以进行无限次，问可以得到的字典序最小的字符串。

注意到条件中 s 的长度是偶数，因此如果 b 是偶数，那么无论轮转多少次，我们都只能给 s 中奇数位的元素做累加操作。但如果 b 是奇数的话，我们可以给 s 中奇数位和偶数位的元素都做加法，并且可以做不同的次数。

从以上可以看出，做累加操作的次数和做轮转操作的次数是互相独立的，做轮转的次数并不会影响到能否对偶数位进行累加。因此我们可以先枚举做轮转的次数，然后再枚举做累加的次数，从而找到字典序最小的答案。

更具体的，我们按照如下步骤进行枚举：

  1. 枚举做轮转的次数，然后令 t 为 s 轮转后的字符串。由于轮转最终会产生循环，且至多轮转 n 次（n 为 s 的长度），因此我们用一个数组 vis 来记录每个位置是否被轮转过。如果遇到之前轮转过的位置，则枚举结束。
  2. 对于每个 t，枚举对 t 的奇数位做累加操作的次数 j，再枚举对 t 的偶数位做累加操作的次数 k。这里因为元素值范围是 [0,9]，因此我们做累加操作的次数上限是 9，再多势必会产生循环。特殊的，如果 b 是偶数，则 k 的上限是 0，否则是 9。

代码

[sol1_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
25
26
27
28
class Solution {
public:
    string findLexSmallestString(string s, int a, int b) {
        int n = s.size();
        vector<int> vis(n);
        string res = s;
        // 将 s 延长一倍，方便截取轮转后的字符串 t
        s = s + s;
        for (int i = 0; vis[i] == 0; i = (i + b) % n) {
            vis[i] = 1;
            for (int j = 0; j < 10; j++) {
                int k_limit = b % 2 == 0 ? 0 : 9;
                for (int k = 0; k <= k_limit; k++) {
                    // 每次进行累加之前，重新截取 t
                    string t = s.substr(i, n);
                    for (int p = 1; p < n; p += 2) {
                        t[p] = '0' + (t[p] - '0' + j * a) % 10;
                    }
                    for (int p = 0; p < n; p += 2) {
                        t[p] = '0' + (t[p] - '0' + k * a) % 10;
                    }
                    res = min(res, t);
                }
            }
        }
        return res;
    }
};
[sol1_1-Java]
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 String findLexSmallestString(String s, int a, int b) {
        int n = s.length();
        boolean[] vis = new boolean[n];
        String res = s;
        // 将 s 延长一倍，方便截取轮转后的字符串 t
        s = s + s;
        for (int i = 0; !vis[i]; i = (i + b) % n) {
            vis[i] = true;
            for (int j = 0; j < 10; j++) {
                int kLimit = b % 2 == 0 ? 0 : 9;
                for (int k = 0; k <= kLimit; k++) {
                    // 每次进行累加之前，重新截取 t
                    char[] t = s.substring(i, i + n).toCharArray();
                    for (int p = 1; p < n; p += 2) {
                        t[p] = (char) ('0' + (t[p] - '0' + j * a) % 10);
                    }
                    for (int p = 0; p < n; p += 2) {
                        t[p] = (char) ('0' + (t[p] - '0' + k * a) % 10);
                    }
                    String tStr = new String(t);
                    if (tStr.compareTo(res) < 0) {
                        res = tStr;
                    }
                }
            }
        }
        return res;
    }
}
[sol1_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
25
26
27
28
29
30
public class Solution {
    public string FindLexSmallestString(string s, int a, int b) {
        int n = s.Length;
        bool[] vis = new bool[n];
        string res = s;
        // 将 s 延长一倍，方便截取轮转后的字符串 t
        s = s + s;
        for (int i = 0; !vis[i]; i = (i + b) % n) {
            vis[i] = true;
            for (int j = 0; j < 10; j++) {
                int kLimit = b % 2 == 0 ? 0 : 9;
                for (int k = 0; k <= kLimit; k++) {
                    // 每次进行累加之前，重新截取 t
                    char[] t = s.Substring(i, n).ToCharArray();
                    for (int p = 1; p < n; p += 2) {
                        t[p] = (char) ('0' + (t[p] - '0' + j * a) % 10);
                    }
                    for (int p = 0; p < n; p += 2) {
                        t[p] = (char) ('0' + (t[p] - '0' + k * a) % 10);
                    }
                    string tStr = new string(t);
                    if (tStr.CompareTo(res) < 0) {
                        res = tStr;
                    }
                }
            }
        }
        return res;
    }
}
[sol1_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
25
26
27
28
29
30
31
32
char * findLexSmallestString(char * s, int a, int b) {
    int n = strlen(s);
    int vis[n];
    memset(vis, 0, sizeof(vis));
    char *res = (char *)calloc(sizeof(char), n + 1);
    strcpy(res, s);
    // 将 s 延长一倍，方便截取轮转后的字符串 t
    char str[2 * n + 1];
    sprintf(str, "%s%s", s, s);
    for (int i = 0; vis[i] == 0; i = (i + b) % n) {
        vis[i] = 1;
        for (int j = 0; j < 10; j++) {
            int k_limit = b % 2 == 0 ? 0 : 9;
            for (int k = 0; k <= k_limit; k++) {
                // 每次进行累加之前，重新截取 t
                char t[n + 1];
                strncpy(t, str + i, n);
                t[n] = '\0';
                for (int p = 1; p < n; p += 2) {
                    t[p] = '0' + (t[p] - '0' + j * a) % 10;
                }
                for (int p = 0; p < n; p += 2) {
                    t[p] = '0' + (t[p] - '0' + k * a) % 10;
                }
                if (strcmp(t, res) < 0) {
                    strcpy(res, t);
                }
            }
        }
    }
    return res;
}
[sol1_1-JavaScript]
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
var findLexSmallestString = function(s, a, b) {
    const n = s.length;
    const vis = new Array(n).fill(false);
    let res = s;
    // 将 s 延长一倍，方便截取轮转后的字符串 t
    s = s + s;
    for (let i = 0; !vis[i]; i = (i + b) % n) {
        vis[i] = true;
        for (let j = 0; j < 10; j++) {
            let kLimit = b % 2 === 0 ? 0 : 9;
            for (let k = 0; k <= kLimit; k++) {
                // 每次进行累加之前，重新截取 t
                const t = [...s.slice(i, i + n)];
                for (let p = 1; p < n; p += 2) {
                    t[p] = String.fromCharCode('0'.charCodeAt() + (t[p].charCodeAt() - '0'.charCodeAt() + j * a) % 10);
                }
                for (let p = 0; p < n; p += 2) {
                    t[p] = String.fromCharCode('0'.charCodeAt() + (t[p].charCodeAt() - '0'.charCodeAt() + k * a) % 10);
                }
                const tStr = t.join('');
                if (tStr < res) {
                    res = tStr;
                }
            }
        }
    }
    return res;
};

枚举轮转次数过程中，我们依次考虑了如下位置：0 \times b \pmod n,1 \times b \pmod n,2 \times b \pmod n,\cdots, x \times b\pmod n。我们可以用一个表达式来计算最终到达的位置：

xb - yn = z

其中 x 是轮转次数，y 是取模过程减去 n 的次数，而 z 是最终到达的位置。

根据裴蜀定理 可知 z 一定是 gcd(b, n) 的倍数，因此我们只需要枚举 [0, n) 中 gcd(b, n) 的倍数即可。

[sol1_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
class Solution {
public:
    string findLexSmallestString(string s, int a, int b) {
        int n = s.size();
        string res = s;
        s = s + s;
        int g = gcd(b, n);
        for (int i = 0; i < n; i += g) {
            for (int j = 0; j < 10; j++) {
                int k_limit = b % 2 == 0 ? 0 : 9;
                for (int k = 0; k <= k_limit; k++) {
                    string t = s.substr(i, n);
                    for (int p = 1; p < n; p += 2) {
                        t[p] = '0' + (t[p] - '0' + j * a) % 10;
                    }
                    for (int p = 0; p < n; p += 2) {
                        t[p] = '0' + (t[p] - '0' + k * a) % 10;
                    }
                    res = min(res, t);
                }
            }
        }
        return res;
    }
};
[sol1_2-Java]
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
class Solution {
    public String findLexSmallestString(String s, int a, int b) {
        int n = s.length();
        String res = s;
        s = s + s;
        int g = gcd(b, n);
        for (int i = 0; i < n; i += g) {
            for (int j = 0; j < 10; j++) {
                int kLimit = b % 2 == 0 ? 0 : 9;
                for (int k = 0; k <= kLimit; k++) {
                    char[] t = s.substring(i, i + n).toCharArray();
                    for (int p = 1; p < n; p += 2) {
                        t[p] = (char) ('0' + (t[p] - '0' + j * a) % 10);
                    }
                    for (int p = 0; p < n; p += 2) {
                        t[p] = (char) ('0' + (t[p] - '0' + k * a) % 10);
                    }
                    String tStr = new String(t);
                    if (tStr.compareTo(res) < 0) {
                        res = tStr;
                    }
                }
            }
        }
        return res;
    }

    public int gcd(int num1, int num2) {
        while (num2 != 0) {
            int temp = num1;
            num1 = num2;
            num2 = temp % num2;
        }
        return num1;
    }
}
[sol1_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
public class Solution {
    public string FindLexSmallestString(string s, int a, int b) {
        int n = s.Length;
        string res = s;
        s = s + s;
        int g = GCD(b, n);
        for (int i = 0; i < n; i += g) {
            for (int j = 0; j < 10; j++) {
                int kLimit = b % 2 == 0 ? 0 : 9;
                for (int k = 0; k <= kLimit; k++) {
                    char[] t = s.Substring(i, n).ToCharArray();
                    for (int p = 1; p < n; p += 2) {
                        t[p] = (char) ('0' + (t[p] - '0' + j * a) % 10);
                    }
                    for (int p = 0; p < n; p += 2) {
                        t[p] = (char) ('0' + (t[p] - '0' + k * a) % 10);
                    }
                    string tStr = new string(t);
                    if (tStr.CompareTo(res) < 0) {
                        res = tStr;
                    }
                }
            }
        }
        return res;
    }

    public int GCD(int num1, int num2) {
        while (num2 != 0) {
            int temp = num1;
            num1 = num2;
            num2 = temp % num2;
        }
        return num1;
    }
}
[sol1_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
int gcd(int num1, int num2) {
    while (num2 != 0) {
        int temp = num1;
        num1 = num2;
        num2 = temp % num2;
    }
    return num1;
}

char * findLexSmallestString(char * s, int a, int b) {
    int n = strlen(s);
    int vis[n];
    memset(vis, 0, sizeof(vis));
    char *res = (char *)calloc(sizeof(char), n + 1);
    strcpy(res, s);
    // 将 s 延长一倍，方便截取轮转后的字符串 t
    char str[2 * n + 1];
    sprintf(str, "%s%s", s, s);
    int g = gcd(b, n);
    for (int i = 0; i < n; i += g) {
        vis[i] = 1;
        for (int j = 0; j < 10; j++) {
            int k_limit = b % 2 == 0 ? 0 : 9;
            for (int k = 0; k <= k_limit; k++) {
                // 每次进行累加之前，重新截取 t
                char t[n + 1];
                strncpy(t, str + i, n);
                t[n] = '\0';
                for (int p = 1; p < n; p += 2) {
                    t[p] = '0' + (t[p] - '0' + j * a) % 10;
                }
                for (int p = 0; p < n; p += 2) {
                    t[p] = '0' + (t[p] - '0' + k * a) % 10;
                }
                if (strcmp(t, res) < 0) {
                    strcpy(res, t);
                }
            }
        }
    }
    return res;
}
[sol1_2-JavaScript]
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
var findLexSmallestString = function(s, a, b) {
    const n = s.length;
    let res = s;
    s = s + s;
    const g = gcd(b, n);
    for (let i = 0; i < n; i += g) {
        for (let j = 0; j < 10; j++) {
            const kLimit = b % 2 === 0 ? 0 : 9;
            for (let k = 0; k <= kLimit; k++) {
                const t = [...s.slice(i, i + n)];
                for (let p = 1; p < n; p += 2) {
                    t[p] = String.fromCharCode('0'.charCodeAt() + (t[p].charCodeAt() - '0'.charCodeAt() + j * a) % 10);
                }
                for (let p = 0; p < n; p += 2) {
                    t[p] = String.fromCharCode('0'.charCodeAt() + (t[p].charCodeAt() - '0'.charCodeAt() + k * a) % 10);
                }
                const tStr = t.join('');
                if (tStr < res) {
                    res = tStr;
                }
            }
        }
    }
    return res;
}

const gcd = (num1, num2) => {
    while (num2 !== 0) {
        const temp = num1;
        num1 = num2;
        num2 = temp % num2;
    }
    return num1;
};

枚举累加次数的过程中，我们的目的是让字符串的字典序更小，由于奇偶位两组互相独立，组内累加次数相同，因此我们只需考虑 t[0] 和 t[1] 即可。

我们先要找到使得 t[1] 最小的轮转次数，对奇数位进行累加。如果 b 是奇数，我们还要找到让 t[0] 最小的轮转次数，对偶数位进行累加。

[sol1_3-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
class Solution {
public:
    string findLexSmallestString(string s, int a, int b) {
        int n = s.size();
        string res = s;
        s = s + s;
        int g = gcd(b, n);
        
        auto add = [&](string& t, int start) {
            int minVal = 10, times = 0;
            for (int i = 0; i < 10; i++) {
                int added = ((t[start] - '0') + i * a) % 10;
                if (added < minVal) {
                    minVal = added;
                    times = i;
                }
            }
            for (int i = start; i < n; i += 2) {
                t[i] = '0' + ((t[i] - '0') + times * a) % 10;
            }
        };

        for (int i = 0; i < n; i += g) {
            string t = s.substr(i, n);
            add(t, 1);
            if (b % 2) {
                add(t, 0);
            }
            res = min(res, t);
        }
        return res;
    }
};
[sol1_3-Java]
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 String findLexSmallestString(String s, int a, int b) {
        int n = s.length();
        String res = s;
        s = s + s;
        int g = gcd(b, n);

        for (int i = 0; i < n; i += g) {
            char[] t = s.substring(i, i + n).toCharArray();
            add(t, n, a, 1);
            if (b % 2 != 0) {
                add(t, n, a, 0);
            }
            String tStr = new String(t);
            if (tStr.compareTo(res) < 0) {
                res = tStr;
            }
        }
        return res;
    }

    public void add(char[] t, int n, int a, int start) {
        int minVal = 10, times = 0;
        for (int i = 0; i < 10; i++) {
            int added = ((t[start] - '0') + i * a) % 10;
            if (added < minVal) {
                minVal = added;
                times = i;
            }
        }
        for (int i = start; i < n; i += 2) {
            t[i] = (char) ('0' + ((t[i] - '0') + times * a) % 10);
        }
    }

    public int gcd(int num1, int num2) {
        while (num2 != 0) {
            int temp = num1;
            num1 = num2;
            num2 = temp % num2;
        }
        return num1;
    }
}
[sol1_3-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
public class Solution {
    public string FindLexSmallestString(string s, int a, int b) {
        int n = s.Length;
        string res = s;
        s = s + s;
        int g = GCD(b, n);

        for (int i = 0; i < n; i += g) {
            char[] t = s.Substring(i, n).ToCharArray();
            Add(t, n, a, 1);
            if (b % 2 != 0) {
                Add(t, n, a, 0);
            }
            string tStr = new string(t);
            if (tStr.CompareTo(res) < 0) {
                res = tStr;
            }
        }
        return res;
    }

    public void Add(char[] t, int n, int a, int start) {
        int minVal = 10, times = 0;
        for (int i = 0; i < 10; i++) {
            int added = ((t[start] - '0') + i * a) % 10;
            if (added < minVal) {
                minVal = added;
                times = i;
            }
        }
        for (int i = start; i < n; i += 2) {
            t[i] = (char) ('0' + ((t[i] - '0') + times * a) % 10);
        }
    }

    public int GCD(int num1, int num2) {
        while (num2 != 0) {
            int temp = num1;
            num1 = num2;
            num2 = temp % num2;
        }
        return num1;
    }
}
[sol1_3-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
int gcd(int num1, int num2) {
    while (num2 != 0) {
        int temp = num1;
        num1 = num2;
        num2 = temp % num2;
    }
    return num1;
}

void add(char *t, int n, int a, int start) {
    int minVal = 10, times = 0;
    for (int i = 0; i < 10; i++) {
        int added = ((t[start] - '0') + i * a) % 10;
        if (added < minVal) {
            minVal = added;
            times = i;
        }
    }
    for (int i = start; i < n; i += 2) {
        t[i] = '0' + ((t[i] - '0') + times * a) % 10;
    }
};

char * findLexSmallestString(char * s, int a, int b) {
    int n = strlen(s);
    int vis[n];
    memset(vis, 0, sizeof(vis));
    char *res = (char *)calloc(sizeof(char), n + 1);
    strcpy(res, s);
    // 将 s 延长一倍，方便截取轮转后的字符串 t
    char str[2 * n + 1];
    sprintf(str, "%s%s", s, s);
    int g = gcd(b, n);
    for (int i = 0; i < n; i += g) {
        char t[n + 1];
        strncpy(t, str + i, n);
        t[n] = '\0';
        add(t, n, a, 1);
        if (b % 2 != 0) {
            add(t, n, a, 0);
        }
        if (strcmp(t, res) < 0) {
            strcpy(res, t);
        }
    }
    return res;
}
[sol1_3-JavaScript]
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
var findLexSmallestString = function(s, a, b) {
    const n = s.length;
    let res = s;
    s = s + s;
    const g = gcd(b, n);

    for (let i = 0; i < n; i += g) {
        const t = [...s.slice(i, i + n)];
        add(t, n, a, 1);
        if (b % 2 !== 0) {
            add(t, n, a, 0);
        }
        const tStr = t.join('');
        if (tStr < res) {
            res = tStr;
        }
    }
    return res;
}

const add = (t, n, a, start) => {
    let minVal = 10, times = 0;
    for (let i = 0; i < 10; i++) {
        const added = ((t[start].charCodeAt() - '0'.charCodeAt()) + i * a) % 10;
        if (added < minVal) {
            minVal = added;
            times = i;
        }
    }
    for (let i = start; i < n; i += 2) {
        t[i] = String.fromCharCode('0'.charCodeAt() + ((t[i].charCodeAt() - '0'.charCodeAt()) + times * a) % 10);
    }
}

const gcd = (num1, num2) => {
    while (num2 !== 0) {
        const temp = num1;
        num1 = num2;
        num2 = temp % num2;
    }
    return num1;
};

复杂度分析

  • 时间复杂度：O(n^2d^2)，其中 n 是 s 的长度，d 是枚举累加次数的上限，本题中等于 10。优化枚举轮转次数后，算法复杂度常数级别降低，在最坏情况下仍然为 O(n^2d^2)。优化枚举累加次数后，时间复杂度降低为 O(n^2d)。

  • 空间复杂度：O(n)，其中 n 是 s 的长度。

 Comments
On this page
1625-执行操作后字典序最小的字符串