class Solution:
def findLexSmallestString(self, s: str, a: int, b: int) -> str:
from collections import deque
seen = set()
queue = deque([s])
ans = s
while queue:
curr = queue.popleft()
if curr < ans:
ans = curr
# Operation 1: add 'a' to all odd indices
curr_list = list(curr)
for i in range(1, len(curr), 2):
curr_list[i] = str((int(curr_list[i]) + a) % 10)
add_a = ''.join(curr_list)
# Operation 2: rotate right by b positions
rotate_b = curr[-b:] + curr[:-b]
for next_str in (add_a, rotate_b):
if next_str not in seen:
seen.add(next_str)
queue.append(next_str)
return ans
class Solution {
public:
string findLexSmallestString(string s, int a, int b) {
unordered_set<string> seen;
queue<string> q;
q.push(s);
seen.insert(s);
string ans = s;
while (!q.empty()) {
string curr = q.front(); q.pop();
if (curr < ans) ans = curr;
// Operation 1: add 'a' to odd indices
string add_a = curr;
for (int i = 1; i < add_a.size(); i += 2) {
add_a[i] = ((add_a[i] - '0' + a) % 10) + '0';
}
// Operation 2: rotate right by b
string rotate_b = curr.substr(curr.size() - b) + curr.substr(0, curr.size() - b);
for (auto& next_str : {add_a, rotate_b}) {
if (!seen.count(next_str)) {
seen.insert(next_str);
q.push(next_str);
}
}
}
return ans;
}
};
import java.util.*;
class Solution {
public String findLexSmallestString(String s, int a, int b) {
Set<String> seen = new HashSet<>();
Queue<String> queue = new LinkedList<>();
queue.add(s);
seen.add(s);
String ans = s;
while (!queue.isEmpty()) {
String curr = queue.poll();
if (curr.compareTo(ans) < 0) ans = curr;
// Operation 1: add 'a' to odd indices
char[] chars = curr.toCharArray();
for (int i = 1; i < chars.length; i += 2) {
chars[i] = (char)(((chars[i] - '0' + a) % 10) + '0');
}
String addA = new String(chars);
// Operation 2: rotate right by b
String rotateB = curr.substring(curr.length() - b) + curr.substring(0, curr.length() - b);
for (String next : new String[]{addA, rotateB}) {
if (seen.add(next)) {
queue.add(next);
}
}
}
return ans;
}
}
/**
* @param {string} s
* @param {number} a
* @param {number} b
* @return {string}
*/
var findLexSmallestString = function(s, a, b) {
let seen = new Set();
let queue = [s];
let ans = s;
seen.add(s);
while (queue.length) {
let curr = queue.shift();
if (curr < ans) ans = curr;
// Operation 1: add 'a' to odd indices
let chars = curr.split('');
for (let i = 1; i < chars.length; i += 2) {
chars[i] = ((parseInt(chars[i]) + a) % 10).toString();
}
let addA = chars.join('');
// Operation 2: rotate right by b
let rotateB = curr.slice(-b) + curr.slice(0, -b);
for (let next of [addA, rotateB]) {
if (!seen.has(next)) {
seen.add(next);
queue.push(next);
}
}
}
return ans;
};
Given a string s consisting of digits, and two integers a and b, you can perform the following operations any number of times and in any order:
a to every digit at an odd index (0-based), modulo 10 (i.e., if the digit becomes greater than 9, it wraps around).b positions (i.e., move the last b characters to the front).Your task is to return the lexicographically smallest string that can be obtained by applying these operations any number of times in any sequence.
Constraints:
s are between '0' and '9'.s.length ≤ 100a, b ≤ 100At first glance, the problem seems to invite brute-force: try every possible sequence of operations, and pick the smallest string. However, with up to 100 digits and repeated operations, the number of possible strings can be extremely large.
We notice that both operations are reversible and can be applied any number of times. This means the set of reachable strings forms a "state space" where each state can be reached from another by applying one of the two operations.
Our goal is to explore all unique strings we can reach, but avoid revisiting the same string multiple times.
This suggests a Breadth-First Search (BFS) or Depth-First Search (DFS) approach, where we systematically apply both operations to every new string, keep track of visited strings, and update our answer whenever we find a smaller string.
To optimize, we use a set or HashSet to record all visited strings, ensuring we never process the same string twice. This prevents infinite loops and redundant work.
s.a to the digit (modulo 10).b positions.This approach guarantees that we will find the lexicographically smallest string, since we systematically explore all reachable strings without redundancy.
Example Input: s = "5525", a = 9, b = 2
The BFS ensures we explore all unique possibilities, and always keep track of the smallest string found.
s.s.length = 100.s), but in practice, it's much smaller due to the structure of the operations.The key insight is that the problem forms a state space where each string can reach others via two reversible operations. By using BFS and a visited set, we efficiently explore all possible unique strings, always keeping track of the smallest one found. This strategy is both systematic and optimal, avoiding brute-force enumeration while guaranteeing the correct answer.
The use of BFS, visited sets, and careful handling of modular arithmetic and rotations makes the solution both robust and elegant.