We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Decrypt String from Alphabet to Integer Mapping

Number: 1434

Difficulty: Easy

Paid? No

Companies: Meta, Quip (Salesforce)

Problem Description

Given a string s composed of digits and '#' characters, decode the string to its English lowercase alphabetical representation. The characters 'a' to 'i' are represented by '1' to '9' respectively, and characters 'j' to 'z' are represented by '10#' to '26#'. The mapping is guaranteed to be unique.

Key Insights

  • The '#' acts as an indicator that the preceding two digits form a number between 10 and 26.
  • Characters without a following '#' represent numbers 1 to 9, which correspond directly to letters 'a' to 'i'.
  • A simple reverse traversal is effective because when you encounter a '#', you know to look two digits backwards.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, as we process each character at most once. Space Complexity: O(n) for the output string.

Solution

We can solve this problem with a single pass through the string by iterating from right to left. This helps in easily handling the '#' characters, as they always follow two digits. When a '#' is encountered, combine the previous two digits to form a two-digit number, map the number to the corresponding letter using the formula (number - 1 + ord('a')), and move the pointer three positions back. If there is no '#' at the current position, convert the single digit to its letter and move one position back. This approach uses simple arithmetic operations and string manipulation.

Code Solutions

# Define the function to decrypt the string using reverse traversal
def freqAlphabets(s: str) -> str:
    # Initialize an empty list to collect decrypted characters
    result = []
    # Start from the end of the string
    i = len(s) - 1
    # Iterate over the string in reverse
    while i >= 0:
        if s[i] == '#':
            # Extract the two digits before '#' and convert to integer
            number = int(s[i-2:i])
            # Map the number to corresponding letter ('a' starts at 97 in ASCII)
            result.append(chr(number + 96))
            # Move the index back by 3 positions since we handled two digits and '#'
            i -= 3
        else:
            # Convert the single digit to its letter representation
            result.append(chr(int(s[i]) + 96))
            # Move the index back by 1 position
            i -= 1
    # Reverse the result list since we appended letters in reverse order and join them into a string
    return ''.join(result[::-1])

# Example usage:
print(freqAlphabets("10#11#12"))  # Expected output: "jkab"
← Back to All Questions