Sum of Digits of String After Convert

EASY

Description

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:

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).
Transform the integer by replacing it with the sum of its digits.
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:

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.

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

Checkout 2 different approaches to solve Sum of Digits of String After Convert. Click on different approaches to view the approach and algorithm in detail.

Brute Force Simulation with Strings

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.

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

The algorithm proceeds as follows:

Initialize a StringBuilder to construct the number string.
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.
After processing all characters, you will have a string, let's call it numStr, representing the converted number.
Start a loop to perform the transformation k times.
In each iteration of the loop, calculate the sum of the digits of the current numStr.
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.
After summing the digits, update numStr to be the string representation of the calculated sum.
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 Analysis

Time Complexity: 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 Complexity: O(N), as a `StringBuilder` and string of length up to 2N are created to store the number after the initial conversion.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Sum of Digits of String After Convert. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Sum of Digits of String After Convert

Data Structures:

String