DEV Community

Ruairí O'Brien
Ruairí O'Brien

Posted on

Day 28 - Smallest String With A Given Numeric Value

The Problem

The numeric value of a lowercase character is defined as its position (1-indexed) in the alphabet, so the numeric value of a is 1, the numeric value of b is 2, the numeric value of c is 3, and so on.

The numeric value of a string consisting of lowercase characters is defined as the sum of its characters' numeric values. For example, the numeric value of the string "abe" is equal to 1 + 2 + 5 = 8.

You are given two integers n and k. Return the lexicographically smallest string with length equal to n and numeric value equal to k.

Note that a string x is lexicographically smaller than string y if x comes before y in dictionary order, that is, either x is a prefix of y, or if I is the first position such that x[i] != y[I], then x[I] comes before y[I] in alphabetic order.

Example 1:

Input: n = 3, k = 27
Output: "aay"
Explanation: The numeric value of the string is 1 + 1 + 25 = 27, and it is the smallest string with such a value and length equal to 3.
Enter fullscreen mode Exit fullscreen mode

Example 2:

Input: n = 5, k = 73
Output: "aaszz"
Enter fullscreen mode Exit fullscreen mode

Constraints:

  • 1 <= n <= 105
  • n <= k <= 26 * n

Tests

import pytest
from .Day28_SmallestStringWithAGivenNumericValue import Solution

s = Solution()


@pytest.mark.parametrize(
    "n,k,expected",
    [
        (3, 27, "aay"),
        (5, 73, "aaszz"),
    ],
)
def test_get_smallest_string(n, k, expected):
    assert s.getSmallestString(n, k) == expected
Enter fullscreen mode Exit fullscreen mode

Solution

from collections import deque


class Solution:
    def getSmallestString(self, n: int, k: int) -> str:
        d = deque()
        i = n - 1
        while i >= 0:
            a = min(k - i, 26)
            d.extendleft(chr(a + ord("a") - 1))
            k -= a
            i -= 1

        return "".join(d)
Enter fullscreen mode Exit fullscreen mode

Analysis

Alt Text

Commentary

My solution performance is terrible!!! I tried doing standard string concatenation but that performed even worse. Not sure what I can do better here. I have a lot to learn. I thought a queue would be quick for building the string with the extend left bit.

The solution itself is straightforward enough. Start from n -1 and work the way back and assign the maximum possible numeric value to a. Prepend that to the queue. At the end convert the queue to a string. 26 is the max possible value since there's 26 letters in the alphabet. We're essentially chopping up z as we go to fit it into n pieces.

Top comments (0)

Postmark Image

Speedy emails, satisfied customers

Are delayed transactional emails costing you user satisfaction? Postmark delivers your emails almost instantly, keeping your customers happy and connected.

Sign up