Skip to content

Lexicographically Smallest Largest

Table of Contents

1323. Maximum 69 Number

3216. Lexicographically Smallest String After a Swap

2697. Lexicographically Smallest Palindrome

2697. Lexicographically Smallest Palindrome - Python Solution
def makeSmallestPalindrome(s: str) -> str:
    n = len(s)
    s = list(s)
    left, right = 0, n - 1

    while left < right:
        if s[left] < s[right]:
            s[right] = s[left]
        elif s[left] > s[right]:
            s[left] = s[right]
        left += 1
        right -= 1

    return "".join(s)


s = "egcfe"
print(makeSmallestPalindrome(s))  # "efcfe"

1881. Maximum Value after Insertion

2734. Lexicographically Smallest String After Substring Operation

1946. Largest Number After Mutating Substring

1663. Smallest String With A Given Numeric Value

1328. Break a Palindrome

1328. Break a Palindrome - Python Solution
# Greedy
def breakPalindrome(palindrome: str) -> str:
    n = len(palindrome)
    if n == 1:
        return ""

    for i in range(n // 2):
        if palindrome[i] != "a":
            return palindrome[:i] + "a" + palindrome[i + 1 :]

    return palindrome[:-1] + "b"


palindrome = "abccba"
print(breakPalindrome(palindrome))  # "aaccba"

2259. Remove Digit From Number to Maximize Result

2566. Maximum Difference by Remapping a Digit

670. Maximum Swap

3106. Lexicographically Smallest String After Operations With Constraint

1053. Previous Permutation With One Swap

2375. Construct Smallest Number From DI String

2182. Construct String With Repeat Limit

  • LeetCode | LeetCode CH (Medium)

  • Tags: hash table, string, greedy, heap priority queue, counting

738. Monotone Increasing Digits

  • LeetCode | LeetCode CH (Medium)

  • Tags: math, greedy

  • Return the largest number that is less than or equal to n with monotone increasing digits.
738. Monotone Increasing Digits - Python Solution
# Greedy
def monotoneIncreasingDigits(n: int) -> int:
    strNum = list(str(n))

    for i in range(len(strNum) - 2, -1, -1):
        if int(strNum[i]) > int(strNum[i + 1]):
            strNum[i] = str(int(strNum[i]) - 1)
            strNum[i + 1 :] = ["9"] * (len(strNum) - (i + 1))

    return int("".join(strNum))


n = 332
print(monotoneIncreasingDigits(n))  # 299

3403. Find the Lexicographically Largest String From the Box I

3170. Lexicographically Minimum String After Removing Stars

1363. Largest Multiple of Three

1754. Largest Merge Of Two Strings

1202. Smallest String With Swaps

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, hash table, string, depth first search, breadth first search, union find, sorting

1202. Smallest String With Swaps - Python Solution
from collections import defaultdict
from typing import List


# Union Find
def smallestStringWithSwaps(s: str, pairs: List[List[int]]) -> str:
    n = len(s)
    par = list(range(n))
    components = defaultdict(list)

    def find(node):
        p = par[node]
        while par[p] != p:
            par[p] = par[par[p]]
            p = par[p]
        return p

    def union(n1, n2):
        p1, p2 = find(n1), find(n2)

        if p1 != p2:
            par[p1] = p2

    for index, j in pairs:
        union(index, j)

    for index in range(n):
        components[find(index)].append(index)

    res = list(s)
    for indices in components.values():
        chars = sorted([s[index] for index in indices])
        for index, char in zip(indices, chars):
            res[index] = char

    return "".join(res)


s = "dcab"
pairs = [[0, 3], [1, 2]]
print(smallestStringWithSwaps(s, pairs))  # "bacd"

2434. Using a Robot to Print the Lexicographically Smallest String

1625. Lexicographically Smallest String After Applying Operations

  • LeetCode | LeetCode CH (Medium)

  • Tags: string, depth first search, breadth first search, enumeration

2948. Make Lexicographically Smallest Array by Swapping Elements

564. Find the Closest Palindrome

1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits

2663. Lexicographically Smallest Beautiful String

3302. Find the Lexicographically Smallest Valid Sequence

555. Split Concatenated Strings

3088. Make String Anti-palindrome

Comments