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:
a to all odd indices of s (0-indexed). Digits post 9 are cycled back to 0. For example, if s = "3456" and a = 5, s becomes "3951".s to the right by b positions. For example, if s = "3456" and b = 1, s becomes "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.length is even.s consists of digits from 0 to 9 only.1 <= a <= 91 <= b <= s.length - 1The key idea is to treat each string configuration as a state. From any state, two operations can be applied: adding a to digits at odd indices (mod 10) and rotating the string to the right by b. These operations form transitions between states, naturally modeling the problem as a graph search.
A practical approach is to explore all reachable states using Breadth-First Search (BFS) or Depth-First Search (DFS). Maintain a visited set to avoid revisiting previously seen strings, since repeated operations can lead to cycles. During traversal, continuously track the lexicographically smallest string encountered.
The search space is bounded because digits wrap around modulo 10 and rotations eventually repeat. This makes exhaustive enumeration feasible. Each state generates at most two new states, and string comparisons determine the best result.
Time Complexity: roughly proportional to the number of reachable states times the string length. Space Complexity:
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| BFS State Exploration | O(N × S) where S is the number of reachable states | O(S × N) for visited states |
| DFS Enumeration | O(N × S) | O(S × N) |
The Code Skool
Use these hints if you're stuck. Try solving on your own first.
Since the length of s is even, the total number of possible sequences is at most 10 * 10 * s.length.
You can generate all possible sequences and take their minimum.
Keep track of already generated sequences so they are not processed again.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
BFS systematically explores all possible states generated by the allowed operations. Since the total number of unique states is limited due to modulo arithmetic and rotation cycles, BFS guarantees that all valid candidates are checked.
Yes, problems involving graph state exploration and string transformations are common in technical interviews. This question tests understanding of BFS/DFS, state deduplication, and lexicographical comparison.
A queue or stack is used for BFS or DFS traversal, and a hash set is essential to store visited string states. This prevents repeated exploration of the same configuration and keeps the search efficient.
The optimal approach models the problem as a state graph and explores all reachable strings using BFS or DFS. By maintaining a visited set, we avoid cycles and track the lexicographically smallest string seen during traversal.