Lexicographically Smallest String After a Swap

Difficulty: Easy | Acceptance: 54.60% | Paid: No Topics: String, Greedy

You are given a string s and an integer k. You can swap any two characters in the string if the absolute difference between their ASCII values is less than or equal to k. You can perform this operation any number of times. Return the lexicographically smallest string you can obtain.

• Examples
• Constraints
• Connected Components (Optimal)
• Greedy Simulation (Alternative)

Examples

Example 1

Input:

s = "45320"

Output:

"43520"

Example 2

Input:

s = "001"

Output:

"001"

Explanation: There is no need to perform a swap because s is already the lexicographically smallest.

Constraints

- 2 <= s.length <= 100
- s consists only of digits.

Connected Components (Optimal)

Intuition The key observation is that characters can only be rearranged freely among themselves if they belong to the same “connected component” based on their ASCII values. Two characters c1 and c2 are in the same component if there exists a sequence of characters between them such that the absolute difference between adjacent characters in the sequence is <= k. Since the alphabet is small (26 letters), we can pre-calculate these components. Characters in different components can never swap places, so their relative order remains fixed. We simply sort the characters within each component to get the lexicographically smallest arrangement.

Steps

• Initialize an array comp_id of size 26 to map each character (0-25) to a component ID.
• Iterate through the alphabet (0 to 25). If the difference between the current character and the previous character is greater than k, increment the current component ID. Assign this ID to the current character.
• Create a list of lists groups to store characters belonging to each component found in the string s.
• Iterate through s, placing each character into its corresponding group based on comp_id.
• Sort each individual group in groups.
• Reconstruct the result string by iterating through s again. For each character, pick the smallest (first) available character from its corresponding group and remove it from the group.

class Solution:\n    def getSmallestString(self, s: str, k: int) -> str:\n        # 1. Assign component IDs to all 26 letters\n        comp_id = [0] * 26\n        curr_comp = 0\n        for i in range(1, 26):\n            # If the gap between current letter and previous is > k,\n            # they belong to different components.\n            if i - (i - 1) > k:\n                curr_comp += 1\n            comp_id[i] = curr_comp\n        \n        # 2. Group characters from s based on their component ID\n        groups = [[] for _ in range(curr_comp + 1)]\n        for char in s:\n            idx = ord(char) - ord('a')\n            groups[comp_id[idx]].append(char)\n        \n        # 3. Sort each group\n        for g in groups:\n            g.sort()\n        \n        # 4. Reconstruct the string\n        # We use pointers to track the next available character in each group\n        pointers = [0] * len(groups)\n        res = []\n        for char in s:\n            idx = ord(char) - ord('a')\n            gid = comp_id[idx]\n            res.append(groups[gid][pointers[gid]])\n            pointers[gid] += 1\n            \n        return 

Complexity

• Time: O(n) or O(n log n). Since the alphabet size is constant (26), sorting the groups takes constant time relative to n. The dominant factor is iterating through the string.
• Space: O(n) to store the groups and the result.
• Notes: This approach is highly efficient due to the constraint on the character set.

Greedy Simulation (Alternative)

Intuition We can simulate the process of building the smallest string character by character. For each position i, we look for the smallest character in the remaining string that can be moved to position i. A character at index j can move to i if it can “bubble” past all characters between i and j. This is possible only if the character’s value is within the allowed range of every character it passes. We maintain a valid range [low, high] that represents the intersection of allowed values for a character to pass through the current block of characters.

Steps

• Convert the string to a list of characters for mutability.
• Iterate through each index i from 0 to n-1.
• For each i, scan j from i to n-1 to find the smallest character that can reach i.
• Maintain low and high bounds. Initially, these are based on s[i]. As we move j, we update the bounds to include s[j-1] (the character that s[j] must pass).
• If s[j] falls within [low, high], it is a candidate. If it is smaller than the current best candidate, update the best.
• After finding the best candidate for position i, swap it to i (shifting intermediate characters to the right).
• Repeat for the next position.

class Solution:\n    def getSmallestString(self, s: str, k: int) -> str:\n        chars = list(s)\n        n = len(chars)\n        \n        for i in range(n):\n            min_char = chars[i]\n            min_idx = i\n            \n            # Range of values that can pass through chars[i...j-1]\n            # Initially, for j=i+1, the block is just chars[i]\n            low = chars[i] - k\n            high = chars[i] + k\n            \n            for j in range(i + 1, n):\n                # Check if chars[j] can pass through chars[i...j-1]\n                if low <= chars[j] <= high:\n                    if chars[j] < min_char:\n                        min_char = chars[j]\n                        min_idx = j\n                \n                # Update range for the next iteration (block includes chars[j])\n                low = max(low, chars[j] - k)\n                high = min(high, chars[j] + k)\n            \n            # If we found a smaller character that can reach i, swap it\n            if min_idx != i:\n                # Shift chars[i...min_idx-1] to the right\n                val = chars[min_idx]\n                chars[i+1:min_idx+1] = chars[i:min_idx]\n                chars[i] = val\n                \n        return \"\".join(chars)\n

Complexity

• Time: O(n²). For each position i, we scan the remaining string.
• Space: O(n) to store the character array.
• Notes: This approach is intuitive and simulates the physical swapping process but is less efficient than the component-based approach for large inputs.