Problem of The Day: Lexicographically Smallest String After Applying Operations

2 min read 579 words

Problem Statement

leetcode problem link

Solution [TLE]

class Solution:
    def __init__(self):
        self.seen = set()

    def findLexSmallestString(self, s: str, a: int, b: int) -> str:
        if s in self.seen:
            return s
        self.seen.add(s)
        def rotate(string):
            k = b % len(string)
            return string[-b:] + string[:-b]

        def add(curr):
            temp = list(curr)
            for i in range(1, len(curr), 2):
                x = (int(temp[i]) + a) % 10
                temp[i] = str(x)
            return ''.join(temp)

        s1 = rotate(s)
        s2 = add(s)

        self.findLexSmallestString(s1, a, b)
        self.findLexSmallestString(s2, a, b)
        return min(self.seen)

Solution [Accepted]

from collections import deque

class Solution:
    def findLexSmallestString(self, s: str, a: int, b: int) -> str:
        n = len(s)

        def rotate(t: str) -> str:
            n = len(t)
            k = b % n
            if k == 0:
                return t
            cut = n - k
            left = t[:cut]
            right = t[cut:]
            return right + left


        def add_odd(t: str) -> str:
            arr = list(t)
            for i in range(1, n, 2):
                arr[i] = str((int(arr[i]) + a) % 10)
            return ''.join(arr)

        ans = s
        q = deque([s])
        seen = {s}

        while q:
            cur = q.popleft()
            if cur < ans:
                ans = cur

            for nxt in (rotate(cur), add_odd(cur)):
                if nxt not in seen:
                    seen.add(nxt)
                    q.append(nxt)

        return ans

• time: O(n^2)
• space: O(n)