LeetCode 1945 - Sum of Digits of String After Convert

This problem asks us to take a string of lowercase English letters and convert it into a numeric value, then repeatedly transform that number by summing its digits.

leetcodeeasystringsimulation

LeetCode Problem 1945

Difficulty: 🟢 Easy
Topics: String, Simulation

Solution

Problem Understanding

This problem asks us to take a string of lowercase English letters and convert it into a numeric value, then repeatedly transform that number by summing its digits.

The first step is a deterministic encoding: each character 'a' through 'z' is mapped to its 1-indexed alphabet position, so 'a' = 1, 'b' = 2, ..., 'z' = 26. These numbers are concatenated together as strings to form one large integer. Importantly, we are not summing these values initially, we are concatenating their decimal representations.

Once we obtain this integer, we repeatedly transform it by replacing it with the sum of its digits. This transformation is applied exactly k times.

The output is the final integer after these repeated digit-sum operations.

The constraints are small: the string length is at most 100 and k is at most 10. This guarantees that even a straightforward simulation is efficient enough, and we do not need any advanced optimization or mathematical shortcuts.

Edge cases are minimal but important: single-character strings, strings that map entirely to single-digit numbers (a to i), and cases where repeated digit sums quickly collapse the number to a single digit (digital root behavior). Another subtle case is that the constructed integer can become large if treated as a number, but since we only process digits, we can safely keep it as a string throughout.

Approaches

Brute Force Approach

The brute force approach directly follows the problem statement. First, convert each character into its numeric representation and concatenate them into a string. Then convert that string into an integer and repeatedly compute the sum of digits k times.

This works because each transformation step is exactly defined, and simulation is straightforward. However, treating the intermediate value as an integer is unnecessary and can be inefficient in other contexts, especially if constraints were larger. The repeated conversion between string and integer also introduces overhead.

Optimal Approach

The optimal approach observes that we never need to treat the full concatenated value as a true integer. Instead, we can keep it as a string and operate directly on its characters. Digit summation is naturally a string-based operation.

This avoids unnecessary integer parsing and keeps the implementation clean. The core insight is that the transformation only depends on digits, so we can simulate everything at the character level efficiently.

Approach Time Complexity Space Complexity Notes
Brute Force O(n + k * d) O(n) Build integer then repeatedly sum digits
Optimal O(n + k * d) O(n) Work directly on digit string without integer conversion

Here n is the length of the expanded digit string and d is its number of digits at each step.

Algorithm Walkthrough

The optimal algorithm proceeds as follows:

  1. Iterate through each character in the input string s and convert it into its alphabet position. For each character, compute ord(c) - ord('a') + 1. Convert this number to a string and append it to a growing result string. This produces the full digit string representation of the encoded input.
  2. Once the full digit string is constructed, we repeatedly apply the digit sum transformation k times. Each transformation involves iterating over every character in the current string, converting it to an integer digit, and summing them.
  3. After computing the sum of digits, we convert the resulting sum back into a string so it can be processed in the next iteration. This ensures uniform handling whether the result has one digit or multiple digits.
  4. Repeat this process exactly k times, updating the working string each time.
  5. After completing all transformations, convert the final string into an integer and return it.

Why it works

The correctness follows directly from the definition of the transformation. The encoding step preserves exact numeric representation in string form, and each transformation step is a pure digit-sum operation. Since digit sum is associative over repeated applications, applying it iteratively k times exactly matches the required process. The algorithm maintains the invariant that the working string always represents the current value in digit form.

Python Solution

class Solution:
    def getLucky(self, s: str, k: int) -> int:
        # Step 1: convert letters to concatenated digit string
        num_str = []
        for ch in s:
            val = ord(ch) - ord('a') + 1
            num_str.append(str(val))
        
        current = "".join(num_str)
        
        # Step 2: apply digit sum k times
        for _ in range(k):
            digit_sum = 0
            for ch in current:
                digit_sum += ord(ch) - ord('0')
            current = str(digit_sum)
        
        return int(current)

Explanation

The code first builds the encoded numeric string using ASCII arithmetic. Each character is mapped to its alphabet index and appended as a string. After joining, we have the full digit sequence.

Then we run a loop k times. In each iteration, we compute the sum of digits by iterating over the string and converting each character to its numeric value. The result is converted back into a string for the next iteration.

Finally, we return the integer value of the final string.

Go Solution

func getLucky(s string) int {
    digits := ""

    for i := 0; i < len(s); i++ {
        val := int(s[i]-'a') + 1
        digits += strconv.Itoa(val)
    }

    for i := 0; i < k; i++ {
        sum := 0
        for j := 0; j < len(digits); j++ {
            sum += int(digits[j] - '0')
        }
        digits = strconv.Itoa(sum)
    }

    result, _ := strconv.Atoi(digits)
    return result
}

Go-specific notes

In Go, string concatenation in a loop is less efficient than using a strings.Builder, but it is acceptable given the small constraints. We also rely on strconv.Itoa and strconv.Atoi for conversions between integers and strings.

One important issue in Go is that repeated string concatenation can be optimized, but here clarity is prioritized. There are no overflow concerns because intermediate values remain small due to digit-sum reduction.

Worked Examples

Example 1: s = "iiii", k = 1

Encoding step:

char value digits
i 9 "9"
i 9 "9"
i 9 "9"
i 9 "9"

Combined string: "9999"

Transformation #1:

current digits sum
"9999" 9 + 9 + 9 + 9 36

Final result after k=1: 36

Example 2: s = "leetcode", k = 2

Encoding:

"l"=12, "e"=5, "e"=5, "t"=20, "c"=3, "o"=15, "d"=4, "e"=5

Concatenation: "12552031545"

Transformation #1:

Digits: 1+2+5+5+2+0+3+1+5+4+5 = 33

Intermediate: "33"

Transformation #2:

3+3 = 6

Final result: 6

Example 3: s = "zbax", k = 2

Encoding:

z=26, b=2, a=1, x=24 → "262124"

Transformation #1:

2+6+2+1+2+4 = 17 → "17"

Transformation #2:

1+7 = 8

Final result: 8

Complexity Analysis

Measure Complexity Explanation
Time O(n + k * d) Encoding takes O(n), each digit sum takes O(d), repeated k times
Space O(n) Storage for the digit string representation

The dominant cost is repeatedly scanning the digit string for summation. Since k is small and the string shrinks quickly, performance remains efficient.

Test Cases

assert Solution().getLucky("iiii", 1) == 36  # example 1 basic case
assert Solution().getLucky("leetcode", 2) == 6  # example 2 multi-step reduction
assert Solution().getLucky("zbax", 2) == 8  # example 3 mixed alphabet mapping
assert Solution().getLucky("a", 1) == 1  # smallest input
assert Solution().getLucky("z", 10) == 8  # repeated digit stability
assert Solution().getLucky("abc", 2) == 6  # multi-character small values
assert Solution().getLucky("i", 1) == 9  # single digit mapping
Test Why
"iiii" verifies repeated identical digits
"leetcode" multi-step transformation correctness
"zbax" mixed 1- and 2-digit encoding
"a" minimum input size
"z" maximum single-character value
"abc" small multi-character case
"i" single-digit encoding stability

Edge Cases

One important edge case is a single-character string. Since such characters map directly to numbers between 1 and 26, the algorithm must correctly handle both single-digit and two-digit encodings without assuming uniform length. The string-based approach naturally handles this.

Another edge case is when the digit sum quickly converges to a single-digit number before k iterations are complete. The algorithm still performs all iterations correctly because summing digits of a single-digit string simply returns the same value.

A third edge case is when repeated concatenation creates varying digit lengths. For example, values like 10, 11, or 26 expand differently. Since we never assume fixed width encoding, and always treat the representation as a string, the implementation remains correct regardless of digit grouping structure.