algoadvance

Leetcode 1309. Decrypt String from Alphabet to Integer Mapping

Problem Statement

You are given a string s formed by digits (‘0’ - ‘9’) and ‘#’. We want to map this string to lowercase characters as follows:

Given a string s, the task is to decrypt it to the original string.

Example:

  1. Input: s = "10#11#12" Output: "jkab"
  2. Input: s = "1326#" Output: "acz"

Clarifying Questions

  1. Length of the string: What can be the maximum length of the string s?
    • Assume that the length of s will be between 1 and 100.
  2. Characters of the string: Will the input string s always be correctly formatted as per the encoding rules?
    • Yes, the string will always follow the rules as stated in the prompt.
  3. Edge cases: How should we handle edge cases?
    • Consider edge cases like the shortest possible input "1" and long sequences without ‘#’.

Strategy

To decrypt the string:

  1. Traverse the string from left to right.
  2. For each character:
    • If you encounter a ‘#’, look at the previous two characters to determine the letter (since ‘#’ denotes a number from 10 to 26).
    • If there’s no ‘#’, it’s a single digit which directly maps to letters ‘a’ to ‘i’.

Code

Here is the C++ code to achieve the solution:

#include <iostream>
#include <string>
#include <vector>

std::string freqAlphabets(std::string s) {
    std::string result;
    int n = s.size();
    
    for (int i = 0; i < n; ++i) {
        if (i + 2 < n && s[i + 2] == '#') {
            // We encountered a number followed by '#', indicating a mapping from 10 to 26
            int number = (s[i] - '0') * 10 + (s[i + 1] - '0');
            result.push_back('a' + number - 1);
            i += 2; // Skip the next two characters as they are part of the current encoding
        } else {
            // Single digit mapping from 1 to 9
            result.push_back('a' + (s[i] - '0') - 1);
        }
    }
    
    return result;
}

int main() {
    std::string s1 = "10#11#12";
    std::string s2 = "1326#";
    std::string s3 = "25#24#23#22#21#20#19#18#17#16#15#14#13#12#11#10#9#8#7#6#5#4#3#2#1#";
    
    std::cout << freqAlphabets(s1) << std::endl; // Outputs: "jkab"
    std::cout << freqAlphabets(s2) << std::endl; // Outputs: "acz"
    std::cout << freqAlphabets(s3) << std::endl; // Outputs: "yxwvutsrqponmlkjihgfedcba"
    
    return 0;
}

Time Complexity

The time complexity of this solution is O(n), where n is the length of the input string s. This is because we traverse the string once, and each operation within the loop takes constant time.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI