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"

Example 2:

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

Example 3:

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

from collections import deque


def solve():
    s = input()
    a = int(input())
    b = int(input())
    n = len(s)
    
    q = deque([s])
    visited = {s}
    min_lex = s
    
    while q:
        curr = q.popleft()
        min_lex = min(min_lex, curr)
        
        # Operation 1: Add 'a' to odd indices
        next_add = list(curr)
        for i in range(1, n, 2):
            next_add[i] = str((int(curr[i]) + a) % 10)
        next_add = "".join(next_add)
        
        if next_add not in visited:
            q.append(next_add)
            visited.add(next_add)
        
        # Operation 2: Rotate by 'b'
        next_rotate = curr[-b:] + curr[:-b]
        if next_rotate not in visited:
            q.append(next_rotate)
            visited.add(next_rotate)
            
    print(min_lex)

solve()

Explanation:

The provided code implements a Breadth-First Search (BFS) approach to find the lexicographically smallest string achievable through the given operations. Here's a breakdown:

1. Initialization:

   • The input string s, and integers a and b are read from input.
   • A deque q is initialized with the original string s. This queue is used for BFS.
   • A set visited is initialized to keep track of visited strings to avoid cycles.
   • min_lex is initialized to s to store the lexicographically smallest string found so far.

2. BFS Loop:

   • The while q loop continues as long as there are strings in the queue to process.
   • In each iteration, the leftmost string curr is dequeued from q.
   • min_lex is updated to the minimum of the current min_lex and curr.

3. Operation 1: Add to Odd Indices:

   • A new string next_add is created by adding a to the odd indices of curr. The modulo operator % 10 is used to cycle digits back to 0 after 9.
   • If next_add has not been visited, it's added to q and visited.

4. Operation 2: Rotate:

   • A new string next_rotate is created by rotating curr to the right by b positions.
   • If next_rotate has not been visited, it's added to q and visited.

5. Output:

   • After the BFS loop finishes, min_lex contains the lexicographically smallest string achievable through the given operations, and it is printed to the console.

Example Walkthrough:

Let's consider s = "5525", a = 9, b = 2

1. Initialization:

   • q = ["5525"]
   • visited = {"5525"}
   • min_lex = "5525"

2. BFS Iteration 1:

   • curr = "5525"
   • min_lex = "5525"
   • next_add = "5424"
   • next_rotate = "2555"
   • q = ["5424", "2555"]
   • visited = {"5525", "5424", "2555"}

3. BFS Iteration 2:

   • curr = "5424"
   • min_lex = "5424"
   • next_add = "5323"
   • next_rotate = "2454"
   • q = ["2555", "5323", "2454"]
   • visited = {"5525", "5424", "2555", "5323", "2454"}

This process continues until the queue q is empty, and the final min_lex is the lexicographically smallest string.

Time and Space Complexity:

• Time Complexity: O(n * 10 * len(s)), where n is the number of possible states. In the worst case, we might visit all possible string configurations. For each configuration, generating new strings using the operations involves iterating over the string, which takes O(len(s)) time.
• Space Complexity: O(n), where n is the number of possible states which can be at most 10 * len(s), to store visited strings in the visited set and the queue q.