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 a Swap

Difficulty: Easy

Problem Description

Given a string s containing only digits, return the lexicographically smallest string that can be obtained after swapping adjacent digits in s with the same parity at most once. Digits have the same parity if both are odd or both are even.

Key Insights

  • The problem requires identifying adjacent digits with the same parity (odd or even).
  • We can only perform one swap, so we need to choose wisely to ensure we get the smallest result.
  • The lexicographical order means we want to arrange numbers in the smallest possible order.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s, since we might need to traverse the string a couple of times.
Space Complexity: O(n), for storing the characters of the string in a list if needed.

Solution

To solve the problem, we can follow these steps:

  1. Traverse the string to identify adjacent digits with the same parity.
  2. For each identified pair, swap them and check if the resulting string is lexicographically smaller than the current smallest string.
  3. Keep track of the smallest string encountered during the swaps.
  4. Return the smallest string found.

We will primarily use a list to store the characters of the string for easy swapping and comparison.

Code Solutions

def lexicographically_smallest_string(s: str) -> str:
    n = len(s)
    smallest = s  # Initialize the smallest with the original string
    chars = list(s)  # Convert string to a list for easy swapping

    for i in range(n - 1):
        # Check for adjacent digits with the same parity
        if (int(chars[i]) % 2) == (int(chars[i + 1]) % 2):
            # Swap the digits
            chars[i], chars[i + 1] = chars[i + 1], chars[i]
            # Create a new string after the swap
            new_string = ''.join(chars)
            # Update smallest if the new string is smaller
            if new_string < smallest:
                smallest = new_string
            # Swap back to restore the original order
            chars[i], chars[i + 1] = chars[i + 1], chars[i]

    return smallest
← Back to All Questions