You are given a string s consisting of lowercase English letters, and an integer k. Your task is to convert the string into an integer by a special process, and then transform it by summing its digits repeatedly k times. More specifically, perform the following steps:
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).k times in total.For example, if s = "zbax" and k = 2, then the resulting integer would be 8 by the following operations:
"zbax" ➝ "(26)(2)(1)(24)" ➝ "262124" ➝ 262124262124 ➝ 2 + 6 + 2 + 1 + 2 + 4 ➝ 1717 ➝ 1 + 7 ➝ 8Return the resulting integer after performing the operations described above.
Example 1:
Input: s = "iiii", k = 1
Output: 36
Explanation:
The operations are as follows:
- Convert: "iiii" ➝ "(9)(9)(9)(9)" ➝ "9999" ➝ 9999
- Transform #1: 9999 ➝ 9 + 9 + 9 + 9 ➝ 36
Thus the resulting integer is 36.
Example 2:
Input: s = "leetcode", k = 2
Output: 6
Explanation:
The operations are as follows:
- 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 resulting integer is 6.
Example 3:
Input: s = "zbax", k = 2
Output: 8
Constraints:
1 <= s.length <= 1001 <= k <= 10s consists of lowercase English letters.Problem Overview: You receive a lowercase string s and an integer k. Each character is converted to its alphabet position (a = 1, b = 2, … z = 26) and concatenated into a numeric string. Then you repeat the digit-sum operation k times. The goal is to return the final integer after these transformations.
Approach 1: Map and Sum Technique (O(n + k * d) time, O(n) space)
This approach directly simulates the process described in the problem. First iterate through the string and convert each character using value = c - 'a' + 1. Append these numbers to build the transformed numeric string. After that, perform the digit-sum operation k times by iterating through the digits and computing their total. The main work comes from scanning the original string once and then processing the digit string repeatedly. This approach is straightforward and mirrors the problem statement, making it easy to implement when practicing string manipulation and simulation.
Approach 2: Direct Digit Sum Accumulation (O(n + k) time, O(1) space)
The key observation: you do not need to build the intermediate numeric string. When converting characters to alphabet positions, immediately split multi-digit values and add their digits to a running sum. For example, z = 26 contributes 2 + 6. This gives the result of the first transformation directly as a digit sum. After that, repeat the digit-sum operation k - 1 times on the resulting number until all iterations are completed. Since only a few digits are processed after the first step, the remaining operations are very small. This optimized simulation avoids storing large strings and keeps space constant while still using simple iteration.
Recommended for interviews: Direct Digit Sum Accumulation is the approach most interviewers expect. It shows you spotted the optimization that eliminates the intermediate string and reduces memory usage. Implementing the basic Map and Sum simulation first demonstrates understanding of the transformation, but the optimized approach proves stronger reasoning with digit manipulation and efficient string processing.
This approach involves converting each character to its corresponding position in the alphabet and forming a numeric string. We then sum the digits of this number 'k' times to get the resulting integer.
The function sumOfDigitsAfterConvert converts the string s into a numeric representation of alphabet positions. The helper function digitSum computes the sum of digits of a given number string. The transformation step is repeated k times by repeatedly summing the digits of the number string.
Time Complexity: O(N + kM), where N is the length of the string and M is the number of digits in the transformed number.
Space Complexity: O(M), as we store the transformed number as a string.
This approach directly calculates the digit sum during the conversion of the string to a number by aggregating the sum of each digit representation, reducing the need for intermediate large integer string handling.
Here, the conversion and the first summing of digits are done simultaneously using modulo operations. This reduces the need for intermediate storage and allows for direct digit sum transformation.
Time Complexity: O(N + k*logM), where M is the intermediate sum value.
Space Complexity: O(1).
We can simulate the process described in the problem.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string s.
| Approach | Complexity |
|---|---|
| Map and Sum Technique | Time Complexity: O(N + kM), where N is the length of the string and M is the number of digits in the transformed number. |
| Direct Digit Sum Accumulation | Time Complexity: O(N + k*logM), where M is the intermediate sum value. |
| Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Map and Sum Technique | O(n + k * d) | O(n) | When implementing the problem exactly as described or when learning basic string-to-number transformations. |
| Direct Digit Sum Accumulation | O(n + k) | O(1) | Best for interviews and production code where avoiding extra string storage improves efficiency. |
1945. Sum of Digits of String After Convert | math | strings | Leetcode Daily Challenge • ShashCode • 3,205 views views
Watch 9 more video solutions →Practice Sum of Digits of String After Convert with our built-in code editor and test cases.
Practice on FleetCode