We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Lexicographically Smallest String After Applying Operations

Number: 1747

Difficulty: Medium

Paid? No

Companies: Amazon, J.P. Morgan

Problem Description

Given an even-length string s consisting of digits [0-9] and two integers a and b, you can perform two operations any number of times in any order:

  1. Add a to every digit at odd indices (0-indexed) with modulo 10 arithmetic.
  2. Rotate the string to the right by b positions. The task is to return the lexicographically smallest string that can be obtained by applying these operations.

Key Insights

  • The "add" operation on odd indices is periodic with a period of 10 since adding a repeatedly will cycle through only 10 possibilities.
  • The "rotate" operation is periodic with a period that depends on the length of s and the value of b, often computed as n/gcd(n, b).
  • The total state space is finite; therefore, we can use a search (BFS or DFS) to explore all possible distinct states.
  • Avoid reprocessing states by using a set to store visited states.
  • The lexicographically smallest string is updated while traversing all states.

Space and Time Complexity

Time Complexity: O(n * 10 * (n / gcd(n, b))), since there are at most 10 possibilities for the add operation and n/gcd(n, b) distinct rotations, with each state requiring O(n) time for processing. Space Complexity: O(n * 10 * (n / gcd(n, b))) for storing the visited states in the worst case.

Solution

We solve the problem using Breadth-First Search (BFS) to explore the state space. We begin with the given string and at each step generate two new states:

  1. One by adding a to all digits at odd indices (using modulo 10 arithmetic).
  2. Another by rotating the string to the right by b positions. A set is used to avoid processing duplicate states. Throughout the BFS, we keep track of the smallest string encountered lexicographically. This systematic exploration guarantees that we will eventually reach the smallest possible string obtainable via the allowed operations.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java with line-by-line comments.

from collections import deque

def findLexSmallestString(s: str, a: int, b: int) -> str:
    # Set to record visited states to avoid repeats
    seen = set()
    # Use deque for BFS traversal
    queue = deque([s])
    seen.add(s)
    # Initialize answer with the original string
    answer = s
    
    # BFS traversal of the state space
    while queue:
        cur = queue.popleft()
        # Update the lexicographically smallest string found so far
        if cur < answer:
            answer = cur
        
        # Operation 1: Add 'a' to all odd-indexed digits (with modulo 10)
        cur_list = list(cur)
        for i in range(1, len(cur_list), 2):
            # Compute new digit with wrap-around using modulo 10
            new_digit = (int(cur_list[i]) + a) % 10
            cur_list[i] = str(new_digit)
        add_state = "".join(cur_list)
        if add_state not in seen:
            seen.add(add_state)
            queue.append(add_state)
        
        # Operation 2: Rotate the string to the right by 'b' positions
        rotated_state = cur[-b:] + cur[:-b]
        if rotated_state not in seen:
            seen.add(rotated_state)
            queue.append(rotated_state)
    
    return answer

# Example usage:
print(findLexSmallestString("5525", 9, 2))  # Expected output: "2050"
← Back to All Questions