add faster solution for 1663

[frankegoesdown]

func getSmallestString(n int, k int) string {
    res := make([]rune, n)
    for i := n - 1; i >= 0; i-- {
        diff := k - i
        if diff >= 26 {
            // Need to add z
            res[i] = 'z'
            k = k - 26
        } else {
            res[i] = rune('a' + diff - 1)
            k = k - diff
        }
    }
    return string(res)
}

func getSmallestString1(n int, k int) string {
    if n == 0 {
        return ""
    }
    res, c := "", []byte{}
    findSmallestString(0, n, k, 0, c, &res)
    return res
}

func findSmallestString(value int, length, k, index int, str []byte, res *string) {
    if len(str) == length && value == k {
        tmp := string(str)
        if (*res) == "" {
            *res = tmp
        }
        if tmp < *res && *res != "" {
            *res = tmp
        }
        return
    }
    if len(str) >= index && (*res) != "" && str[index-1] > (*res)[index-1] {
        return
    }
    for j := 0; j < 26; j++ {
        if k-value > (length-len(str))*26 || value > k {
            return
        }
        str = append(str, byte(int('a')+j))
        value += j + 1
        findSmallestString(value, length, k, index+1, str, res)
        str = str[:len(str)-1]
        value -= j + 1

    }
}

And my solution example:

func getSmallestString2(n int, k int) string {
    var result = make([]byte, n)
    for pos := n - 1; pos >= 0; pos-- {
        add := min(k - pos, 26)
        result[pos] = byte(add) + 'a' - 1
        k -= add
    }
    return string(result)
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

as you can see it shows more perfomance

[codecov-io]

Codecov Report

:exclamation: No coverage uploaded for pull request base (master@65d2fd6). Click here to learn what that means. The diff coverage is n/a.

@@            Coverage Diff            @@
##             master      #95   +/-   ##
=========================================
  Coverage          ?   71.60%           
=========================================
  Files             ?      578           
  Lines             ?    10395           
  Branches          ?        0           
=========================================
  Hits              ?     7443           
  Misses            ?     2671           
  Partials          ?      281           

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 65d2fd6...74ef066. Read the comment docs.

[halfrost]

Thank you for your solution. I optimized your solution again. Like your solution, the solution idea is greed. The time complexity of our solution is the same, both are O(n), and optimization is only constant-level optimization. My solution beats 100%. This is my new code:

func getSmallestString(n int, k int) string {
    str, i, j := make([]byte, n), 0, 0
    for i = n - 1; i <= k-26; i, k = i-1, k-26 {
        str[i] = 'z'
    }
    if i >= 0 {
        str[i] = byte('a' + k - 1 - i)
        for ; j < i; j++ {
            str[j] = 'a'
        }
    }
    return string(str)
}

[frankegoesdown]

Looks great and clean

[halfrost]

This solution time complexity is the same with you. Only reduced the number of loops.