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

Smallest String With A Given Numeric Value

Number: 1782

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given two integers n and k, construct the lexicographically smallest string of length n such that the sum of its characters' numeric values (where 'a' = 1, 'b' = 2, ..., 'z' = 26) equals k.

Key Insights

  • Start with a string filled with the smallest character 'a', which gives the minimum possible sum of n.
  • Calculate the remaining value to be distributed by subtracting n from k.
  • Modify the string from the end (rightmost position) to maintain lexicographical order, replacing 'a' with higher characters as needed.
  • At each position, determine the maximum increment possible (up to 25) without overshooting the remaining value.
  • Continue until the remaining value is fully distributed.

Space and Time Complexity

Time Complexity: O(n) - Each character is processed at most once. Space Complexity: O(n) - We use an array (or similar structure) of length n to build the output string.

Solution

The approach uses a greedy method:

  1. Initialize a result list with n 'a's (each with a value of 1), leading to an initial sum of n.
  2. Calculate the extra value (k - n) that needs to be distributed to reach the desired sum.
  3. Iterate over the list from the end (to maintain lexicographical order) and at each step, add as much value as possible (up to 25 more than 'a') without exceeding the extra value.
  4. Replace the character at the current position with the new character corresponding to the added value.
  5. Reduce the remaining extra value accordingly.
  6. Continue until no extra value remains, then join and return the string.

Code Solutions

# Python solution

def getSmallestString(n, k):
    # Initialize list with 'a' for minimum sum
    result = ['a'] * n
    # Calculate remaining sum after assigning 'a' to each position
    remaining = k - n

    # Process positions from end of the string for lexicographical order
    index = n - 1
    while remaining > 0:
        # Determine the addition for the current position (max is 25, corresponding to 'z')
        add = min(25, remaining)
        # Update the character at the current index
        result[index] = chr(ord('a') + add)
        # Decrease the remaining value
        remaining -= add
        index -= 1

    # Join list to form the final string
    return "".join(result)

# Example usage:
print(getSmallestString(3, 27))  # Expected output: "aay"
← Back to All Questions