algoadvance

You are given a string s formed only by digits (‘0’-‘9’) and ‘#’. We want to map s to a string according to the following rules:

1. Characters (‘a’ to ‘i’) are represented by (‘1’ to ‘9’) respectively.
2. Characters (‘j’ to ‘z’) are represented by (‘10#’ to ‘26#’) respectively.

Return the string formed after mapping.

Example:

Input: s = "10#11#12"
Output: "jkab"

Input: s = "1326#"
Output: "acz"

Follow the string rules to decrypt it appropriately.

Clarifying Questions

• Q: Will the input string s always be valid according to the rules given (digits or ‘#’)?
  • A: Yes, you can assume that the input string will always be valid according to the rules.
• Q: What is the maximum length of the string s?
  • A: The problem doesn’t specify but typically for such problems, we can assume length up to 10^4.

Strategy

1. Initialize a result list that will store the characters as we decode them.
2. Iterate through the string from the end to the start:
   • Check if the current character is ‘#’:
     • If it is, get the two preceding characters to form a number between 10 and 26.
     • Convert this number to the corresponding letter (‘j’ to ‘z’).
     • Skip the next two characters.
   • If it is not ‘#’:
     • Convert the digit to the corresponding letter (‘a’ to ‘i’).
3. Continue this process until you have iterated through the entire string.
4. Join the characters in the result list to form the final decrypted string and return it.

Code

def freqAlphabets(s: str) -> str:
    result = []
    i = len(s) - 1
    
    while i >= 0:
        if s[i] == '#':
            num = int(s[i-2:i])
            char = chr(num + 96)
            result.append(char)
            i -= 3
        else:
            num = int(s[i])
            char = chr(num + 96)
            result.append(char)
            i -= 1
            
    return ''.join(result[::-1])

# Testing the example cases
print(freqAlphabets("10#11#12"))  # Output: "jkab"
print(freqAlphabets("1326#"))     # Output: "acz"

Time Complexity

• Time Complexity: O(n), where n is the length of the input string. We process each character at most once.
• Space Complexity: O(n), where n is the length of the input string. We store the result as a list of characters that will later be joined and returned as a string.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?