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 Operations With Constraint

Number: 3346

Difficulty: Medium

Paid? No

Companies: ServiceNow

Problem Description

Given a string s and an integer k, you can change any letter in s to any other lowercase letter any number of times. Changing a letter incurs a cost defined as the minimum distance between the two letters on a cyclic alphabet (i.e. the distance from 'a' to 'z' is 1). The task is to find a string t — lexicographically smallest possible — such that the sum of costs to change s into t does not exceed k.

Key Insights

  • The cost to change a letter from x to y is given by: cost = min(|x - y|, 26 - |x - y|).
  • To obtain the lexicographically smallest result, try to change each character in s to the smallest possible letter (starting from 'a') if the cost is within the remaining budget.
  • Since you are allowed to not spend the entire available budget, you always have the option of leaving a character unchanged (cost 0).
  • Process the string from left to right and for each position, search for the smallest candidate letter (strictly smaller than the current letter) that can be achieved with the remaining k; if none is possible, leave the letter unchanged.

Space and Time Complexity

Time Complexity: O(n * 26) where n is the length of the string (n ≤ 100).
Space Complexity: O(n) for storing the result (or O(1) if done in-place).

Solution

The solution uses a greedy approach. For each character in the string (from left to right), we iterate over the candidate letters starting from 'a' up to the character just before the current character (because a candidate equal to the current letter produces no lexicographic improvement). For each candidate letter, we calculate the cyclic distance between the current character and the candidate. If the cost does not exceed the remaining budget k, we choose that candidate, reduce k by the cost, and move to the next character. If no candidate letter (that is lexicographically smaller) can be chosen within the budget, we leave the character unchanged.

Data structures used are simple variables (for the result and k) and the algorithm relies on iterative greedy decisions based on the cost function.

Code Solutions

# Python solution

def lex_smallest_string(s: str, k: int) -> str:
    # Function to compute cyclic distance between two letters.
    def cyclic_distance(char_from, char_to):
        diff = abs(ord(char_from) - ord(char_to))
        return min(diff, 26 - diff)
    
    result = []  # List to store resulting characters.
    
    # Process each character in the string.
    for char in s:
        # Try from 'a' to character before current one.
        replaced = False
        for candidate in map(chr, range(ord('a'), ord(char))):
            cost = cyclic_distance(char, candidate)
            # If the candidate letter is reachable given the current budget,
            # choose it and update the remaining budget.
            if cost <= k:
                result.append(candidate)
                k -= cost
                replaced = True
                break
        # If no candidate letter is suitable, leave the letter unchanged.
        if not replaced:
            result.append(char)
    return "".join(result)

# Example runs
print(lex_smallest_string("zbbz", 3))  # Expected "aaaz"
print(lex_smallest_string("xaxcd", 4)) # Expected "aawcd"
print(lex_smallest_string("lol", 0))   # Expected "lol"
← Back to All Questions