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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Lexicographically Smallest String After Applying Operations

Difficulty: Medium

Problem Description

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:

  1. Add a to all odd indices of s (0-indexed). Digits post 9 are cycled back to 0.
  2. Rotate s to the right by b positions.

Return the lexicographically smallest string you can obtain by applying the above operations any number of times on s.

Key Insights

  • The operations can be combined in various sequences, impacting the final string.
  • The first operation modifies specific indices, while the second operation shifts the entire string.
  • As the string is of even length, the digits at odd indices can be controlled independently through the first operation.
  • To find the smallest string, both operations can be explored effectively through enumeration of states.

Space and Time Complexity

Time Complexity: O(n^2) - In the worst case, we might need to explore all rotations (O(n)) and for each rotation apply the operations leading to O(n) transformations.

Space Complexity: O(n) - We store the transformed strings and possibly the states explored.

Solution

The solution involves generating all possible rotations of the string and applying the addition operation on odd indices for each rotation. We then compare the results to find the lexicographically smallest string.

  1. For every possible rotation of the string, apply the addition operation iteratively until the string stabilizes (i.e., no further changes can be made).
  2. Keep track of the smallest string encountered.

The data structure used is a list to hold the transformed strings, and the algorithm follows a brute-force approach to enumerate all possible states.

Code Solutions

def add_to_odds(s, a):
    # Convert string to list for mutability
    s_list = list(s)
    for i in range(1, len(s_list), 2):
        # Add 'a' and cycle back to '0' after '9'
        s_list[i] = str((int(s_list[i]) + a) % 10)
    return ''.join(s_list)

def rotate(s, b):
    b = b % len(s)  # Normalize b
    return s[-b:] + s[:-b]

def lexicographically_smallest_string(s, a, b):
    n = len(s)
    smallest = s
    # Generate all rotations
    for i in range(n):
        rotated_s = rotate(s, i)
        # Apply the addition operation until no change occurs
        current = rotated_s
        while True:
            next_s = add_to_odds(current, a)
            if next_s == current:  # No change
                break
            current = next_s
        smallest = min(smallest, current)  # Track the smallest string
    return smallest
← Back to All Questions