Problem of The Day: Lexicographically Smallest String After Applying Operations

Problem Statement

leetcode problem link

Brute Force [Accepted]

class Solution:
    def findLexSmallestString(self, s: str, a: int, b: int) -> str:
        list_s = list(s)
        N = len(s)
        seen = set()
        def rotate_b(arr):
            ans = []
            for i in range(N):
                idx = (i + b) % N
                ans.append(arr[idx])
            return ans

        def add_a(arr):
            ans = arr[:]
            for i in range(1, N, 2):
                ans[i] = str((int(arr[i]) + a) % 10)
            return ans

        def compare(arr1, arr2):
            for c1, c2 in zip(arr1, arr2):
                x, y = int(c1), int(c2)
                if x == y:
                    continue
                if x < y:
                    return arr1
                else:
                    return arr2

            return arr1

        def dfs(curr):
            if ''.join(curr) in seen:
                return
            seen.add(''.join(curr))
            arr1 = rotate_b(curr)
            dfs(arr1)
            arr2 = add_a(curr)
            dfs(arr2)
            return

        dfs(list(s))
        res = sorted(list(seen))
        return res[0]

Editorial

Approach: Enumeration

class Solution:
    def findLexSmallestString(self, s: str, a: int, b: int) -> str:
        n = len(s)
        vis = [False] * n
        res = s
        # double the length of s for convenience in extracting the rotated string t
        s = s + s
        i = 0
        while not vis[i]:
            vis[i] = True
            for j in range(10):
                k_limit = 0 if b % 2 == 0 else 9
                for k in range(k_limit + 1):
                    # before each accumulation, re-truncate t
                    t = list(s[i : i + n])
                    for p in range(1, n, 2):
                        t[p] = str((int(t[p]) + j * a) % 10)
                    for p in range(0, n, 2):
                        t[p] = str((int(t[p]) + k * a) % 10)
                    t_str = "".join(t)
                    if t_str < res:
                        res = t_str
            i = (i + b) % n
        return res

class Solution:
    def findLexSmallestString(self, s: str, a: int, b: int) -> str:
        n = len(s)
        res = s
        s = s + s
        g = math.gcd(b, n)
        for i in range(0, n, g):
            for j in range(10):
                k_limit = 0 if b % 2 == 0 else 9
                for k in range(k_limit + 1):
                    t = list(s[i : i + n])
                    for p in range(1, n, 2):
                        t[p] = str((int(t[p]) + j * a) % 10)
                    for p in range(0, n, 2):
                        t[p] = str((int(t[p]) + k * a) % 10)
                    t_str = "".join(t)
                    if t_str < res:
                        res = t_str
        return res

class Solution:
    def findLexSmallestString(self, s: str, a: int, b: int) -> str:
        n = len(s)
        res = s
        s = s + s
        g = math.gcd(b, n)

        def add(t, start):
            original = int(t[start])
            min_val, times = 10, 0
            for i in range(10):
                added = (original + i * a) % 10
                if added < min_val:
                    min_val = added
                    times = i
            t_list = list(t)
            for i in range(start, n, 2):
                t_list[i] = str((int(t_list[i]) + times * a) % 10)
            return "".join(t_list)

        for i in range(0, n, g):
            t = s[i : i + n]
            t = add(t, 1)
            if b % 2:
                t = add(t, 0)
            if t < res:
                res = t
        return res