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

难度: Medium

给你一个字符串 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

Submission

运行时间: 79 ms

内存: 0.0 MB

@cache
def generate(num, a):
    lst = [((num+i*a)%10, i) for i in range(10)]
    return min(lst, key=lambda x: x[0])[1]
    
class Solution:
    def findLexSmallestString(self, s: str, a: int, b: int) -> str:
        s = [int(i) for i in s]
        n = len(s)
        res = []
        seen = set()
        for i in range(n):
            offset = i*b % n
            if offset in seen:
                break
            seen.add(offset)
            lst = s[n-offset:] + s[:n-offset]
            t = generate(lst[1], a)
            for j in range(1, n, 2):
                lst[j] = (lst[j] + t*a) % 10
            if b % 2 == 1:
                t = generate(lst[0], a)
                for j in range(0, n, 2):
                    lst[j] = (lst[j] + t*a) % 10
            res.append(''.join([str(i) for i in lst]))
        # print(res)
        return min(res)

Explain

这个题解利用了循环串的概念和数字的周期性。首先，定义了一个辅助函数 generate(num, a) 来找出对于一个给定的数字 num，在累加操作下，如何通过最小的变化使其达到最小的可能值。接着在主函数中，通过旋转和累加操作，尝试生成所有可能的字符串变体。具体步骤包括：将字符串 s 转换为整数数组，然后对每个可能的旋转位移进行遍历，每次旋转后再对奇数位执行累加操作，如果 b 是奇数，也对偶数位执行累加操作，最后将所有可能的字符串收集起来，返回其中字典序最小的字符串。这种方法考虑了通过不同的旋转和累加操作来探索所有可能的字符串配置，并利用集合来避免重复处理相同的旋转配置。

时间复杂度: O(n^2)

空间复杂度: O(n^2)

from functools import lru_cache

@lru_cache
def generate(num, a):
    # 生成从0到9的数字在累加a后的最小值对应的累加次数
    lst = [((num+i*a)%10, i) for i in range(10)]
    return min(lst, key=lambda x: x[0])[1]
    
class Solution:
    def findLexSmallestString(self, s: str, a: int, b: int) -> str:
        # 将字符串转换为整数数组
        s = [int(i) for i in s]
        n = len(s)
        res = []
        seen = set()
        # 对每个可能的旋转位移进行处理
        for i in range(n):
            offset = i*b % n
            if offset in seen:
                break
            seen.add(offset)
            # 计算旋转后的新数组
            lst = s[n-offset:] + s[:n-offset]
            # 找到使奇数位最小的累加次数
            t = generate(lst[1], a)
            for j in range(1, n, 2):
                lst[j] = (lst[j] + t*a) % 10
            # 如果b是奇数，也对偶数位进行累加操作
            if b % 2 == 1:
                t = generate(lst[0], a)
                for j in range(0, n, 2):
                    lst[j] = (lst[j] + t*a) % 10
            # 记录当前变体字符串
            res.append(''.join([str(i) for i in lst]))
        # 返回字典序最小的字符串
        return min(res)

Explore

这是基于模运算的性质和数字的周期性。在十进制系统中，任何数字加上10的倍数都不会改变其在模10运算中的结果。因此，一个数字`num`在累加`a`后，考虑其模10的结果只需考察`num`, `num+a`, `num+2a`, ..., `num+9a`这10个数字即可，因为`num+10a`的模10结果会和`num`相同，从而形成周期。通过这10次迭代，我们可以找到令`num`模10的结果最小的`a`的累加次数。

旋转配置的处理是基于旋转偏移量`offset`的。在处理字符串旋转时，旋转偏移量`offset`是通过`i*b % n`计算得出的，其中`i`是当前的旋转尝试次数，`b`是旋转步长，而`n`是字符串的长度。如果某个计算出的偏移量已经在之前出现过（即存在于集合`seen`中），则意味着该旋转已经被考虑过，因此可以跳过以避免重复处理。这样确保每种旋转配置只被处理一次，提高了算法的效率和避免了不必要的重复计算。

这一操作是基于旋转步长`b`的奇偶性对字符串中字符位置的影响。当`b`是奇数时，偶数索引和奇数索引的字符会在旋转过程中交替出现，这意味着原本在偶数位置的字符因为旋转可以出现在奇数位置上，反之亦然。因此，为了确保在所有可能的字符串配置中找到字典序最小的结果，当`b`为奇数时，我们需要对偶数位和奇数位的数字进行累加操作。这样可以确保不论字符如何旋转，都能考虑到其可能被累加修改的情况，从而生成所有可能的字符串配置，最终选取字典序最小的一个。