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

Smallest String With A Given Numeric Value

Difficulty: Medium

Problem Description

You are given two integers n and k. Return the lexicographically smallest string with length equal to n and numeric value equal to k, where the numeric value of a string is defined as the sum of its characters' numeric values, with 'a' = 1, 'b' = 2, ..., 'z' = 26.

Key Insights

  • The string must have exactly n characters.
  • The sum of the numeric values of the characters must equal k.
  • To achieve the lexicographically smallest string, start with 'a' and use larger characters towards the end of the string.
  • The maximum numeric value for a single character is 26 (for 'z'), which restricts how many characters can be used to reach k.

Space and Time Complexity

Time Complexity: O(n) - We iterate through the length of the string to construct it. Space Complexity: O(n) - The space used to store the result string.

Solution

The approach involves greedy construction of the string:

  1. Initialize a result list of size n filled with 'a'.
  2. Start from the end of the list and work backwards to maximize the character values while keeping the total equal to k.
  3. At each position, determine the maximum character that can be placed without exceeding the remaining required numeric value (k).
  4. Update the current position with the calculated character and adjust k accordingly.

Code Solutions

def smallestString(n: int, k: int) -> str:
    # Initialize a list with 'a' (1) repeated n times
    result = ['a'] * n
    
    # Start filling from the end of the list
    for i in range(n - 1, -1, -1):
        # Calculate the maximum value we can assign to this position
        max_value = min(26, k - (n - 1 - i))  # Ensure not to exceed remaining k
        result[i] = chr(ord('a') + max_value - 1)  # Set character
        k -= max_value  # Decrease k by the value assigned
        
    return ''.join(result)  # Convert list back to string
← Back to All Questions