Problem

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 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.

Examples

Example 1:

1
2
3
4
5
6

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:

1
2
3
4
5
6
7

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:

1
2

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

Solution

Method 1 - Iteration

Here are the steps:

  1. Convert each character in the string s to its corresponding position in the alphabet.
  2. Concatenate these positions to form a new string.
  3. Sum the digits of this string k times or until a single digit is obtained.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public class Solution {
    // Main method to perform the conversion
    public int getLucky(String s, int k) {
        // Step 1: Convert each character to its alphabet position
        StringBuilder numSb = new StringBuilder();
        for (char ch : s.toCharArray()) {
	        int num = ch - 'a' + 1;
            numSb.append(num);
        }

        // Step 2: Sum digits `k` times
        String currStr = numSb.toString();
        for (int i = 0; i < k; i++) {
            currStr = sumOfDigits(currStr);
            if (currStr.length() == 1) {
                break;
            }
        }

        return Integer.parseInt(currStr);
    }    

    // Helper method to sum the digits of a number represented as a string
    private String sumOfDigits(String numStr) {
        int sum = 0;
        for (char digit : numStr.toCharArray()) {
            sum += Character.getNumericValue(digit);
        }
        return Integer.toString(sum);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def getLucky(self, s: str, k: int) -> int:
        def get_alphabet_position(char):
            return ord(char) - ord("a") + 1

        # Step 1: Convert each character to its alphabet position
        numeric_string = "".join(str(get_alphabet_position(char)) for char in s)

        # Function to sum the digits of a number represented as a string
        def sum_of_digits(num_str):
            return str(sum(int(digit) for digit in num_str))

        # Step 2: Sum digits `k` times
        for _ in range(k):
            numeric_string = sum_of_digits(numeric_string)
            if len(numeric_string) == 1:
                break

        return int(numeric_string)

Complexity

  • ⏰ Time complexity: O(k*n), where k is the number of iterations to sum digits, and n is the length of the input string s.
    • StringBuilder numericString can have a length up to 2n (assuming each alphabet position is a 2-digit number like ‘10’ to ‘26’). Hence, space required is O(n).
    • During k iterations of summing the digits, the largest space consumption happens initially when the numeric string is largest (2n). After each summing step, the length of the string reduces.
  • 🧺 Space complexity: O(n)