Sum of Digits of String After Convert

Difficulty: Easy | Acceptance: 74.80% | Paid: No Topics: String, Simulation

You are given a string s consisting of lowercase English letters, and an integer k.

First, convert s into an integer by replacing each letter with its position in the alphabet (i.e., replace ‘a’ with 1, ‘b’ with 2, …, ‘z’ with 26). Then, transform the integer by replacing it with the sum of its digits. Repeat the transform operation k times in total.

For example, if s = “zbax” and k = 2, then:

Convert: “zbax” ➝ “(26)(2)(1)(24)” ➝ “262124” ➝ 262124 Transform #1: 262124 ➝ 2 + 6 + 2 + 1 + 2 + 4 ➝ 17 Transform #2: 17 ➝ 1 + 7 ➝ 8

Return the resulting integer after performing the operations described above.

• Examples
• Constraints
• Approach 1: String Simulation
• Approach 2: Mathematical Optimization

Examples

Example 1:

Input: s = "iiii", k = 1
Output: 36
Explanation: 
Convert: "iiii" ➝ "(9)(9)(9)(9)" ➝ "9999" ➝ 9999
Transform #1: 9999 ➝ 9 + 9 + 9 + 9 ➝ 36
Thus the result is 36.

Example 2:

Input: s = "leetcode", k = 2
Output: 6
Explanation:
Convert: "leetcode" ➝ "(12)(5)(5)(20)(3)(15)(4)(5)" ➝ "12552031545" ➝ 12552031545
Transform #1: 12552031545 ➝ 1 + 2 + 5 + 5 + 2 + 0 + 3 + 1 + 5 + 4 + 5 ➝ 33
Transform #2: 33 ➝ 3 + 3 ➝ 6
Thus the result is 6.

Example 3:

Input: s = "zbax", k = 2
Output: 8

Constraints

1 <= s.length <= 100
1 <= k <= 10
s consists of lowercase English letters.

Approach 1: String Simulation

Intuition Follow the problem statement literally by first converting the string to a numeric string, then repeatedly summing its digits.

Steps

• Iterate through the input string s and append the string representation of each character’s alphabet position to a new string num_str.
• Loop k times. In each iteration, calculate the sum of all digits in num_str, update num_str to be this sum converted to a string.
• Return the integer value of num_str.

class Solution:
    def getLucky(self, s: str, k: int) -> int:
        # Convert string to integer string
        num_str = ""
        for ch in s:
            val = ord(ch) - ord('a') + 1
            num_str += str(val)
        
        # Perform k transformations
        for _ in range(k):
            total = 0
            for digit in num_str:
                total += int(digit)
            num_str = str(total)
            
        return int(num_str)

Complexity

• Time: O(k * n), where n is the length of the intermediate string.
• Space: O(n) to store the intermediate string.
• Notes: Simple to implement but creates unnecessary string objects.

Approach 2: Mathematical Optimization

Intuition We can avoid building the large intermediate string by calculating the sum of digits directly from the character values during the first pass.

Steps

• Initialize total to 0.
• Iterate through s. For each character, calculate its value (1-26). Add the digits of this value (e.g., for 26, add 2 and 6) to total. This completes the first transformation.
• Loop k - 1 more times. In each loop, calculate the sum of digits of total and update total.
• Return total.

class Solution:
    def getLucky(self, s: str, k: int) -> int:
        # First transformation: sum digits of letter values
        total = 0
        for ch in s:
            val = ord(ch) - ord('a') + 1
            total += val % 10 + val // 10
        
        # Remaining k-1 transformations
        for _ in range(k - 1):
            next_total = 0
            while total > 0:
                next_total += total % 10
                total //= 10
            total = next_total
            
        return total

Complexity

• Time: O(n + k * log(result)), where n is the length of s.
• Space: O(1) extra space.
• Notes: More efficient as it avoids string manipulation overhead.