#1625

Lexicographically Smallest String After Applying Operations

pupil · 485 · lc medium +27 · verified · 79.4% accepted · 689 likes · top 91%

⚑ DFS / BFS: Connected Components & Reachability

Description

Given a string s of even length made of digits 0-9, and integers a and b, apply these operations in any order any number of times: (1) add a to all odd-indexed digits modulo 10; (2) rotate the string right by b positions. Return the lexicographically smallest string reachable.

Example 1:

Input: s = "5525", a = 9, b = 2

Output: "2050"

Explanation: We can apply the following operations:

Start: "5525"

Rotate: "2555"

Add: "2454"

Add: "2353"

Rotate: "5323"

Add: "5222"

Add: "5121"

Rotate: "2151"

Add: "2050"

There is no way to obtain a string that is lexicographically smaller than "2050".

Example 2:

Input: s = "74", a = 5, b = 1

Output: "24"

Explanation: We can apply the following operations:

Start: "74"

Rotate: "47"

Add: "42"

Rotate: "24"

There is no way to obtain a string that is lexicographically smaller than "24".

Example 3:

Input: s = "0011", a = 4, b = 2

Output: "0011"

Explanation: There are no sequence of operations that will give us a lexicographically smaller string than "0011".

Code

1

2

3

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

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