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

Difficulty: Medium

Problem Description

You are given a string s and an integer k. You can change any letter of s to any other lowercase English letter, any number of times. Return a string denoting the lexicographically smallest string t you can get after some changes, such that distance(s, t) <= k, where distance is defined as the sum of the minimum distances between corresponding characters in a cyclic order.

Key Insights

  • The distance between two characters can be computed using their cyclic positions in the alphabet.
  • To achieve the lexicographically smallest string, we should prioritize changing characters to 'a' whenever possible.
  • The number of changes allowed is constrained by the value of k, which dictates how many total changes can be made.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s. Space Complexity: O(n), for storing the resulting string.

Solution

The solution involves iterating through each character of the string s and determining how many changes can be made to minimize the character lexicographically. If k allows changing the current character to 'a', we do so. If not, we calculate the maximum possible change to the current character without exceeding k. The resulting characters are collected to form the final string.

Code Solutions

def lexicographically_smallest_string(s: str, k: int) -> str:
    n = len(s)
    result = []
    
    for char in s:
        if k > 0:
            # Calculate the distance to 'a'
            distance_to_a = (ord(char) - ord('a')) % 26
            if distance_to_a <= k:
                result.append('a')
                k -= distance_to_a
            else:
                # Change to the closest character within remaining k
                new_char = chr(ord(char) - k)
                result.append(new_char)
                k = 0
        else:
            result.append(char)
    
    return ''.join(result)
← Back to All Questions