Leetcode Daily Question 03/09/2024 - 1945. Sum of Digits of String After Convert

Problem Description:

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.

class Solution:
  def getLucky(self, s: str, k: int) -> int:
    k_string = ""
    for char in s:
      k_string += str(ord(char) - 96)
    
    dSum = 0
    for _ in range(k):
      dSum = 0
      for char in k_string:
        dSum += int(char)
      k_string = str(dSum)
      
    return dSum

Explanation:

We can solve this by following the instruction carefully.

First we turn string s into a number string character by character. To turn each letter into its corresponding number, we utilise the in-built ord() method.

The ord() method returns the unique ascii identifier of the character string passed into it. Lowercase letter represents the range 97-122 in ascii.

Since the question dictates that our letter-number conversion is 1-index, we subtract 96 from the order of each character to get the letter-number conversion.

k_string = ""
for char in s:
  k_string += str(ord(char) - 96)

All there is left is to compute the digit sum k_string k times.

We can do this by keeping track of the sum for each iteration and put k_string as the "stringified" number we have after each iteration.

dSum = 0
for _ in range(k):
  dSum = 0 # resets the sum everytime
  for char in k_string:
    dSum += int(char)
  k_string = str(dSum)
  
return dSum

The time complexity is O(k * n). Since each character is converted to at most 2 digits, the maximum total time length for each conversion is O(2n). We do this k times, so the total time complexity is O(k * 2n) = O(k * n)

The space complexity is O(n). As mentioned, each character is converted to at most 2 digits.

The full solution can be found near the top of the page.