Lexicographically Smallest String After Applying Operations
MedPrompt
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
ato all odd indices ofs(0-indexed). Digits post9are cycled back to0. For example, ifs = "3456"anda = 5,sbecomes"3951". - Rotate
sto the right bybpositions. For example, ifs = "3456"andb = 1,sbecomes"6345".
Return the lexicographically smallest string you can obtain by applying the above operations any number of times on s.
A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b. For example, "0158" is lexicographically smaller than "0190" because the first position they differ is at the third letter, and '5' comes before '9'.
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".
Constraints:
2 <= s.length <= 100s.lengthis even.sconsists of digits from0to9only.1 <= a <= 91 <= b <= s.length - 1
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses a recursive Depth-First Search (DFS) to explore all possible strings that can be generated. Starting with the initial string, it recursively explores the outcomes of applying the 'add' and 'rotate' operations. A Set is used to keep track of visited strings to prevent infinite loops and avoid re-processing the same string, making the exploration efficient.
Algorithm
- Initialize a global variable
minStringwith the input strings. - Create a
Set<String>calledvisitedto keep track of processed strings to avoid cycles and redundant computations. - Define a recursive function
dfs(String current). - Inside
dfs(current):- If
currentis already invisited, return immediately. - Add
currentto thevisitedset. - Compare
currentwithminString. Ifcurrentis lexicographically smaller, updateminString. - Apply the 'add' operation to
currentto getaddString. Make a recursive call:dfs(addString). - Apply the 'rotate' operation to
currentto getrotateString. Make a recursive call:dfs(rotateString).
- If
- Start the process by calling
dfs(s)from the main function. - After the recursion completes,
minStringwill hold the result.
Walkthrough
The problem of finding the lexicographically smallest string can be modeled as finding a specific node in a state-space graph. Each unique string is a node, and the operations are edges. A Depth-First Search is a natural way to traverse this graph.
We start a recursive traversal from the initial string s. A global variable, minString, is maintained to store the lexicographically smallest string found so far. To make the search efficient and to prevent getting stuck in cycles (e.g., rotating n/b times by b gets back to the original string), we use a HashSet to store all the strings (states) we have already visited.
In each step of the recursion, we take the current string, check if it's smaller than our current minString, and update if necessary. Then, we generate two new strings by applying the 'add' and 'rotate' operations. For each new string, we make a recursive call only if it has not been visited before. This ensures that every reachable state is processed exactly once.
import java.util.HashSet;import java.util.Set; class Solution { String minString; Set<String> visited; int a; int b; public String findLexSmallestString(String s, int a, int b) { this.minString = s; this.visited = new HashSet<>(); this.a = a; this.b = b; dfs(s); return minString; } private void dfs(String s) { if (visited.contains(s)) { return; } visited.add(s); if (s.compareTo(minString) < 0) { minString = s; } // Apply add operation dfs(applyAdd(s)); // Apply rotate operation dfs(applyRotate(s)); } private String applyAdd(String s) { char[] chars = s.toCharArray(); for (int i = 1; i < chars.length; i += 2) { int digit = chars[i] - '0'; digit = (digit + a) % 10; chars[i] = (char) (digit + '0'); } return new String(chars); } private String applyRotate(String s) { int n = s.length(); return s.substring(n - b) + s.substring(0, n - b); }}Complexity
Time
O(S * n), where `S` is the number of reachable states and `n` is the string length. Each state is processed once, and processing involves string operations that take O(n) time. The number of states `S` is bounded by `(n/gcd(n,b)) * (10/gcd(a,10))`, which is at most `10n`. Thus, the time complexity is O(n^2).
Space
O(S * n), where `S` is the number of reachable states and `n` is the string length. The space is used for the `visited` set and the recursion stack. Since `S` is at most `10n`, the complexity is O(n^2).
Trade-offs
Pros
The logic is straightforward to implement for those familiar with recursion and graph traversal.
It is guaranteed to find the correct lexicographically smallest string by exploring all reachable states.
Cons
If the state space graph is deep, this approach can lead to a
StackOverflowErrordue to deep recursion. The maximum recursion depth could be up to the total number of states.While having the same theoretical time complexity as BFS, the overhead of function calls in recursion can sometimes be slightly higher than the iterative approach of BFS.
This approach models the problem as finding a node in a state-space graph. Each unique string that can be generated is a node, and the two operations ('add' and 'rotate') represent directed edges. We start from the initial string s and explore all reachable strings using an iterative Breadth-First Search (BFS). By keeping track of visited strings in a Set, we ensure each state is processed only once, making the algorithm efficient.
Algorithm
- Initialize a
Queue<String>and add the initial stringsto it. - Initialize a
Set<String>calledvisitedand addsto it. This set will store all strings that have been enqueued to prevent processing them again. - Initialize a string variable
minStringtos. - Loop while the queue is not empty:
- Dequeue a string, let's call it
current. - Compare
currentwithminString. Ifcurrentis lexicographically smaller, updateminString. - Apply the 'add' operation on
currentto getaddString. IfaddStringhas not been visited, add it to thevisitedset and enqueue it. - Apply the 'rotate' operation on
currentto getrotateString. IfrotateStringhas not been visited, add it to thevisitedset and enqueue it.
- Dequeue a string, let's call it
- After the loop terminates (when all reachable states have been visited),
minStringholds the result.
Walkthrough
A Breadth-First Search (BFS) is an ideal algorithm for systematically exploring all reachable states from a starting point, which is exactly what this problem requires. We can think of the initial string s as the root of a graph, and the 'add' and 'rotate' operations as ways to discover new, connected nodes (strings).
We use a queue to manage the order of strings to visit, ensuring that we explore the graph level by level. A HashSet is used to keep track of visited strings to avoid redundant computations and infinite loops.
The process begins by adding the initial string s to both the queue and the visited set. We also initialize our answer, minString, to s. Then, we repeatedly dequeue a string, apply the two operations to generate potential new strings, and if a generated string hasn't been visited, we add it to our visited set and the queue. Every string taken from the queue is compared with minString to find the lexicographically smallest one.
The efficiency of this approach hinges on the total number of unique strings we can generate. The number of distinct rotations is at most n. For any given string, the 'add' operation can produce at most 10 unique variants (as adding a ten times cycles back). The total number of reachable states is bounded by (n/gcd(n,b)) * (10/gcd(a,10)), which is at most 10n. Given n <= 100, the state space is small enough for this approach to be very fast.
import java.util.HashSet;import java.util.LinkedList;import java.util.Queue;import java.util.Set; class Solution { public String findLexSmallestString(String s, int a, int b) { Queue<String> queue = new LinkedList<>(); Set<String> visited = new HashSet<>(); String minString = s; queue.offer(s); visited.add(s); while (!queue.isEmpty()) { String current = queue.poll(); if (current.compareTo(minString) < 0) { minString = current; } // Apply add operation char[] addChars = current.toCharArray(); for (int i = 1; i < addChars.length; i += 2) { int digit = addChars[i] - '0'; digit = (digit + a) % 10; addChars[i] = (char) (digit + '0'); } String added = new String(addChars); if (visited.add(added)) { queue.offer(added); } // Apply rotate operation int n = current.length(); String rotated = current.substring(n - b) + current.substring(0, n - b); if (visited.add(rotated)) { queue.offer(rotated); } } return minString; }}Complexity
Time
O(S * n), where `S` is the number of reachable states and `n` is the string length. Each of the `S` states is processed once. Processing involves string creation, comparison, and hashing, each taking O(n) time. Since `S` is at most `10n`, the total time complexity is O(n^2).
Space
O(S * n), where `S` is the number of reachable states and `n` is the string length. Space is dominated by the `visited` set and the `queue`. Since `S` is at most `10n`, the complexity is O(n^2).
Trade-offs
Pros
Guaranteed to find the lexicographically smallest string by exhaustively and efficiently exploring all possibilities.
Avoids deep recursion and the risk of stack overflow, making it more robust than a recursive DFS for graphs with long paths.
The time and space complexity are very good for the given constraints due to the small size of the state space.
Cons
Requires extra space for the queue and the visited set, which can be significant if the number of states is large, although it's manageable for this problem's constraints.
Solutions
Solution
class Solution {public String findLexSmallestString(String s, int a, int b) { Deque<String> q = new ArrayDeque<>(); q.offer(s); Set<String> vis = new HashSet<>(); vis.add(s); String ans = s; int n = s.length(); while (!q.isEmpty()) { s = q.poll(); if (ans.compareTo(s) > 0) { ans = s; } char[] cs = s.toCharArray(); for (int i = 1; i < n; i += 2) { cs[i] = (char)(((cs[i] - '0' + a) % 10) + '0'); } String t1 = String.valueOf(cs); String t2 = s.substring(n - b) + s.substring(0, n - b); for (String t : List.of(t1, t2)) { if (vis.add(t)) { q.offer(t); } } } return ans; }}class Solution {public: string findLexSmallestString(string s, int a, int b) { queue<string> q{{s}}; unordered_set<string> vis{{s}}; string ans = s; int n = s.size(); while (!q.empty()) { s = q.front(); q.pop(); ans = min(ans, s); string t1 = s; for (int i = 1; i < n; i += 2) { t1[i] = (t1[i] - '0' + a) % 10 + '0'; } string t2 = s.substr(n - b) + s.substr(0, n - b); for (auto &t : {t1, t2}) { if (!vis.count(t)) { vis.insert(t); q.emplace(t); } } } return ans; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.