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

Number: 3484

Difficulty: Easy

Paid? No

Companies: J.P. Morgan

Problem Description

Given a string s composed only of digits, you are allowed to perform at most one swap between any two adjacent digits if they have the same parity (both digits are even or both are odd). The goal is to obtain the lexicographically smallest string possible.

Key Insights

  • Only adjacent swaps are allowed.
  • The swap can only be done if both digits share the same parity.
  • You can perform at most one swap.
  • Check every possible valid adjacent swap and choose the one that produces the smallest string.
  • If no swap improves the string, return the original string.

Space and Time Complexity

Time Complexity: O(n^2), where n is the length of the string (each swap operation involves copying the string for comparison). Space Complexity: O(n) for storing candidate strings.

Solution

The approach involves iterating through the string and checking each pair of adjacent digits to see if they have the same parity. For every valid pair:

  1. Create a new candidate string by swapping the two digits.
  2. Compare the candidate with the current best result.
  3. Keep track of the lexicographically smallest string. If no swap yields improvement, return the original string.

Data structures used include basic string manipulation functions and arrays (or lists) for converting strings when needed. The algorithm is essentially greedy, as it evaluates all one-time swap possibilities and picks the optimal result.

Code Solutions

# Python solution for Lexicographically Smallest String After a Swap

def smallestString(s: str) -> str:
    # Initialize the best string as the original input
    best = s

    # Iterate through the string and check each adjacent pair
    for i in range(len(s) - 1):
        # Check if the two adjacent characters have the same parity (both even or both odd)
        if (int(s[i]) % 2 == int(s[i+1]) % 2):
            # Convert the string to a list for swapping since strings are immutable
            s_list = list(s)
            # Swap the two adjacent digits
            s_list[i], s_list[i+1] = s_list[i+1], s_list[i]
            # Form the new candidate string after swap
            candidate = ''.join(s_list)
            # Update the best candidate if the new string is lexicographically smaller
            if candidate < best:
                best = candidate
    return best

# Example test cases
print(smallestString("45320"))  # Output: "43520"
print(smallestString("001"))    # Output: "001"
← Back to All Questions