Lexicographically Smallest String After Applying Operations — LeetCode 1625 Python Solution

MediumDepth-First SearchBreadth-First SearchStringEnumeration

Problem: #1625
Pattern: Breadth-First Search
Reading time: 3 min
Source: leetcode.com

The problem

You are given a string s of even length consisting of digits from 0 to 9, and two integers a and b. You can apply either of the following two operations any number of times and in any order on s: Add a to all odd indices of s (0-indexed).

Example

Input: s = "5525", a = 9, b = 2
Output: "2050"
Explanation: We can apply the following operations:

Python solution

Python

class Solution:
    def findLexSmallestString(self, s: str, a: int, b: int) -> str:
        q = deque([s])
        vis = {s}
        ans = s
        while q:
            s = q.popleft()
            if ans > s:
                ans = s
            t1 = ''.join(
                [str((int(c) + a) % 10) if i & 1 else c for i, c in enumerate(s)]
            )
            t2 = s[-b:] + s[:-b]
            for t in (t1, t2):
                if t not in vis:
                    vis.add(t)
                    q.append(t)
        return ans

Complexity

Measure	Complexity
Time	O(n^2 \times 10^2)
Space	O(n), where n is the length of string s auxiliary

Pattern: Breadth-First Search

Expand outward level by level, so the first time you arrive is the shortest way. LeetCode 1625. Lexicographically Smallest String After Applying Operations is filed here because LeetCode tags it Breadth-First Search, which is the vocabulary this hub collects.

The breadth-first search guide has the Python template for the pattern and the 233 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1625. Lexicographically Smallest String After Applying Operations?: LeetCode 1625. Lexicographically Smallest String After Applying Operations is rated Medium on LeetCode.
What is the time complexity of LeetCode 1625. Lexicographically Smallest String After Applying Operations?: The Python solution on this page runs in O(n^2 \times 10^2).
What is the space complexity of LeetCode 1625. Lexicographically Smallest String After Applying Operations?: The Python solution on this page uses O(n), where n is the length of string s auxiliary space.
What topics does LeetCode 1625. Lexicographically Smallest String After Applying Operations cover?: LeetCode 1625. Lexicographically Smallest String After Applying Operations is tagged Depth-First Search, Breadth-First Search, String and Enumeration on LeetCode.