Scale Engineer

Sum of Digits of String After Convert

Easy
#1774Time: O(N + k * L), where N is the length of the input string `s` and L is the length of the number string. The initial conversion is O(N). The first transformation operates on a string of length up to 2N. Subsequent transformations are on much smaller numbers. The complexity is dominated by the initial conversion and the first transformation, making it effectively O(N), but with higher constant factors due to string operations.Space: O(N), as a `StringBuilder` and string of length up to 2N are created to store the number after the initial conversion.
Data structures
String

Prompt

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:

  1. 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).
  2. Transform the integer by replacing it with the sum of its digits.
  3. Repeat the transform operation (step 2) k times in total.

For example, if s = "zbax" and k = 2, then the resulting integer would be 8 by the following operations:

  1. Convert: "zbax" ➝ "(26)(2)(1)(24)" ➝ "262124" ➝ 262124
  2. Transform #1: 262124 ➝ 2 + 6 + 2 + 1 + 2 + 4 ➝ 17
  3. Transform #2: 17 ➝ 1 + 7 ➝ 8

Return 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 <= 100
  • 1 <= k <= 10
  • s consists of lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem statement. It first converts the input string s into a new, potentially very long, string of digits. Then, it iteratively calculates the sum of digits of this string k times, updating the string at each step.

Algorithm

  • Create a StringBuilder to store the numeric representation of the string s.
  • Iterate through s, converting each character c to c - 'a' + 1 and appending it to the StringBuilder.
  • Convert the StringBuilder to a string numStr.
  • Loop k times:
    • Calculate the sum of digits of numStr.
    • Update numStr with the string representation of the sum.
  • Return the final sum as an integer.

Walkthrough

The core idea is to use string manipulation to handle the large number generated in the 'convert' step.

The algorithm proceeds as follows:

  1. Initialize a StringBuilder to construct the number string.
  2. Iterate through each character of the input string s. For each character c, find its corresponding alphabetical position (e.g., 'a' -> 1, 'b' -> 2). Append this numeric value to the StringBuilder.
  3. After processing all characters, you will have a string, let's call it numStr, representing the converted number.
  4. Start a loop to perform the transformation k times.
  5. In each iteration of the loop, calculate the sum of the digits of the current numStr.
  6. To do this, initialize a sum variable to 0. Iterate through the characters of numStr, convert each character to its integer value, and add it to sum.
  7. After summing the digits, update numStr to be the string representation of the calculated sum.
  8. After k iterations, the final numStr holds the string representation of the answer. Convert it to an integer and return.

Here is the Java implementation for this approach:

class Solution {    public int getLucky(String s, int k) {        StringBuilder sb = new StringBuilder();        for (char c : s.toCharArray()) {            sb.append(c - 'a' + 1);        }        String numStr = sb.toString();        long sum = 0;         // Perform the transformation k times        for (int i = 0; i < k; i++) {            sum = 0;            for (char digitChar : numStr.toCharArray()) {                sum += digitChar - '0';            }            numStr = String.valueOf(sum);        }        return (int) sum;    }}

Complexity

Time

O(N + k * L), where N is the length of the input string `s` and L is the length of the number string. The initial conversion is O(N). The first transformation operates on a string of length up to 2N. Subsequent transformations are on much smaller numbers. The complexity is dominated by the initial conversion and the first transformation, making it effectively O(N), but with higher constant factors due to string operations.

Space

O(N), as a `StringBuilder` and string of length up to 2N are created to store the number after the initial conversion.

Trade-offs

Pros

    • The logic is straightforward and directly follows the problem description, making it easy to understand and implement.

Cons

    • This approach is inefficient because it involves creating a potentially large intermediate string.
    • Repeated conversions between strings and numbers inside the loop add performance overhead.

Solutions

class Solution {public  int getLucky(String s, int k) {    StringBuilder sb = new StringBuilder();    for (char c : s.toCharArray()) {      sb.append(c - 'a' + 1);    }    s = sb.toString();    while (k-- > 0) {      int t = 0;      for (char c : s.toCharArray()) {        t += c - '0';      }      s = String.valueOf(t);    }    return Integer.parseInt(s);  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem