1945. Sum of Digits of String After Convert

Description

Given a string s consisting of lowercase English letters, you first convert each letter to its position in the alphabet (e.g., 'a' -> 1, 'b' -> 2, etc.). Then you concatenate these numbers to form a single number. After that, you perform a transformation k times where, in each transformation, you replace the number with the sum of its digits. The goal is to return the resulting number after k transformations.

Intuition

The problem requires two main operations:

1. Converting characters to their corresponding numeric values.
2. Summing the digits of a number multiple times.

The key observation is that the transformation reduces the number's size in each step, making it more manageable after a few iterations. The repetitive nature of summing digits is an indicator that the problem can be solved efficiently even with multiple iterations.

Approach

1. Convert the String: Start by converting each character in the string s to its corresponding position in the alphabet. Concatenate these values to form a large number in string format.
2. Sum the Digits: Perform the transformation k times, where each transformation involves summing the digits of the current number and updating the number to this sum.
3. Return the Result: After k transformations, the number will be reduced to a single-digit or small number, which is returned as the final result.

Complexity

Time Complexity:

• The initial conversion of the string s to its numeric form is O(n), where n is the length of s.
• Each transformation to sum the digits is O(m), where m is the number of digits in the current number. Given k transformations, the total complexity is O(n + k * m).

Space Complexity:

O(1) if we consider only the extra space for storing numeric values, since all operations are done in place (excluding the input and output).

Code

C++

class Solution {
public:
    int getLucky(string s, int k) {
        string value = "";
        for (char c : s) {
            value += to_string(c - 'a' + 1);
        }
        
        while (k-- > 0) {
            int v = 0;
            for (char c : value) {
                v += c - '0';
            }
            value = to_string(v);
        }
        
        return stoi(value);
    }
};

Python

class Solution:
    def getLucky(self, s: str, k: int) -> int:
        value = ''.join(str(ord(c) - 96) for c in s)
        
        while k > 0:
            v = sum(int(digit) for digit in value)
            value = str(v)
            k -= 1
            
        return int(value)

Java

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

JavaScript

var getLucky = function (s, k) {
    let value = '';
    for (i = 0; i < s.length; i++) {
        value += s.charCodeAt(i) - 96
    }
    do {
        let v = 0
        for (i = 0; i < value.length; i++)
            v += Number(value[i])
        value = v.toString();
        k--;
    } while (k > 0);
    return value;
};