1945. Sum of Digits of String After Convert

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.

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.

Approach 01:

#include <iostream>
#include <string>
using namespace std;

class Solution {
public:
    int getLucky(string s, int k) {
        string numericString = "";
        
        // Convert each character in the input string to its numeric equivalent
        for (char ch : s) {
            int numericValue = (ch - 'a' + 1);
            numericString += to_string(numericValue);
        }

        // Sum the digits for k iterations
        for (int i = 0; i < k; ++i) {
            int digitSum = 0;
            for (char digit : numericString) {
                digitSum += digit - '0'; // Convert character to integer
            }
            numericString = to_string(digitSum);
        }

        return stoi(numericString);
    }
};

class Solution:
    def getLucky(self, s: str, k: int) -> int:
        numericString = ''
        
        # Convert each character in the input string to its numeric equivalent
        for char in s:
            numericValue = ord(char) - ord('a') + 1
            numericString += str(numericValue)
        
        # Sum the digits for k iterations
        for _ in range(k):
            digitSum = sum(int(digit) for digit in numericString)
            numericString = str(digitSum)
        
        return int(numericString)

Time Complexity

• Conversion to Numeric String:

  Converting each character in the input string s to its numeric equivalent involves iterating over the entire string, which takes \( O(n) \) time, where n is the length of the string s.

• Sum of Digits Calculation:

  For each of the k iterations, the solution calculates the sum of the digits in the numeric string. If the initial numeric string length is m (the combined length of numeric equivalents of all characters in s), the sum calculation takes \( O(m) \) time. Therefore, the time complexity for the digit sum calculation across k iterations is \( O(k \cdot m) \).

• Overall Time Complexity:

  The overall time complexity is \( O(n + k \cdot m) \), where n is the length of the input string and m is the length of the numeric string generated from s.

Space Complexity

• Space for Numeric String:

  The solution uses a string numericString to store the numeric representation of the input string, which has a maximum length of \( O(2n) \) because each character in s is converted to a number that can have up to 2 digits. Thus, the space complexity for storing the numeric string is \( O(n) \).

• Overall Space Complexity:

  The overall space complexity is \( O(n) \), which is used to store the numeric representation of the input string.