{x}
blog image

Lexicographically Smallest String After Applying Operations

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). Digits post 9 are cycled back to 0. For example, if s = "3456" and a = 5, s becomes "3951".
  • Rotate 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 <= 100
  • s.length is even.
  • s consists of digits from 0 to 9 only.
  • 1 <= a <= 9
  • 1 <= b <= s.length - 1

Solution Explanation for Lexicographically Smallest String After Applying Operations

This problem asks to find the lexicographically smallest string that can be obtained by applying two operations repeatedly to a given string s. The operations are:

  1. Add a to odd indices: Add integer a to each digit at an odd index (0-indexed). Digits wrap around from 9 to 0.
  2. Rotate right by b: Rotate the string to the right by b positions.

Approach 1: Breadth-First Search (BFS)

This approach uses BFS to explore all possible strings reachable from the initial string s. We keep track of visited strings to avoid cycles.

Algorithm:

  1. Initialization: Start with a queue q containing the initial string s and a set vis to store visited strings (initially containing only s). Initialize ans to s.

  2. BFS Loop: While the queue is not empty:

    • Dequeue a string s from q.
    • Update ans if s is lexicographically smaller.
    • Apply operation 1 (add a to odd indices) to get t1.
    • Apply operation 2 (rotate right by b) to get t2.
    • For both t1 and t2, if they haven't been visited, add them to q and vis.

  3. Return: Return ans.

Time Complexity: O(N * 10N), where N is the length of the string. In the worst case, we might explore all possible strings obtained by applying the operations. The exponential part comes from the repeated application of operations.

Space Complexity: O(N * 10N) in the worst case to store all visited strings.

Approach 2: Optimized Iteration

This approach cleverly iterates through possible rotations and avoids explicit BFS, reducing the space complexity. It leverages the fact that applying operation 1 multiple times leads to a cycle of length 10 for each odd-indexed digit, and that the rotations cover all possible shifts.

Algorithm:

  1. Initialization: Initialize ans to s.

  2. Outer Loop (Rotations): Iterate n times (where n is the length of s), each time rotating the string to the right by b.

  3. Inner Loop (Adding a): Iterate 10 times to explore all possible combinations of adding a to odd indices. This covers all the possible cyclic variations from adding a multiple times.

  4. Conditional Inner Loop (Even indices): If b is odd, add another inner loop to apply the operation to even indices (for odd b, the odd and even indices will be cycled after rotation).

  5. Update ans: After each combination of adding a, check if the current string is lexicographically smaller than ans and update if necessary.

Time Complexity: O(N * 102), where N is the string length. This is significantly faster than BFS, as it avoids explicitly storing the entire search space.

Space Complexity: O(N), primarily for the string.

Code Examples (Python, Java, C++, Go)

The code examples provided earlier demonstrate both approaches. Approach 1 (BFS) is more straightforward, while Approach 2 (optimized iteration) is significantly more efficient, particularly for longer strings. Choose the approach that best suits your needs regarding code clarity versus performance. The time and space complexities are analyzed above.