Decode String Frequency Amazon OA Solution

Decode String Frequency Amazon OA Solution

Amazon Web Services (AWS) is working on a new security feature to help encode text. Consider a string that consists of lowercase English alphabetic letters (i.e., [a-z]) only. The following rules are used to encode all of its characters into string s:

• a is encoded as 1, b is encoded as 2, c is encoded as 3, …, and i is encoded as 9.
• j is encoded as 10#, k is encoded as 11#, l is encoded as 12#, …, and z is encoded as 26#.
• If there are two or more consecutive occurrences of any character, then the character count is written within parentheses (i.e., (c), where c is an integer denoting the count of consecutive occurrences being encoded) immediately following the encoded character. For example, consider the following string encodings:
  • String “abzx” encoded as s = “1226#24#”.
  • String “aabccc” is encoded as s = “1(2)23(3)”.
  • String “bajj” is encoded as s = “2110#(2)”.
  • String “wwxyzwww” is encoded as s = “23#(2)24#25#26#23#(3)”.

Given an encoded string s, determine the character counts for each letter of the original, decoded string. Return an integer array of length 26 where index 0 contains the number of ‘a’ characters, index 1 contains the number of ‘b’ characters and so on.

Input

s: an encoded string

Output

an array of 26 integers as described

Examples

Example 1:

Input: 1s = 1226#24#

Output: “

Explanation:

String “abzx” encoded as s = “1226#24#”.

Constraints

• String s consists of decimal integers from 0 to 9, #, and ()s only.
• 1<=length of s<=10^5.
• It is guaranteed that string s is a valid encoded string.
• 2<=c<=10^4, where c is a parenthetical count of consecutive occurrences of an encoded character.

SOLUTION

Program: Decode String Frequency Amazon OA Solution in C++

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

using namespace std;

class Solution {
public:
    // Time Complexity: O(N)
    // Space Complexity: O(1)
    vector<int> frequency(string encodedString) {
        vector<int> res(26, 0);
        if (encodedString.empty()) {
            return res;
        }

        // 2(2) repeated chars
        // 10#  10 - 26 chars
        // 1    1 - 9
        int N = encodedString.size();
        int i = N - 1;

        bool repeated = false;
        int repeatedCnt = 0;

        while(i >= 0) {
            char c = encodedString[i];
            if (c == ')') {
                // find until (
                //  ...i-1
                int r = i - 1;
                int l = r;
                while(l >= 0 && encodedString[l] != '(') {
                    l--;
                }
                if (l <= 0) {
                    // must be invalid input, left must have char 
                    break; 
                }

                // encodeString[l] == '('
                auto repStr = encodedString.substr(l + 1, r - (l + 1) + 1);

                // find left until new char
                i = l - 1;

                // record repeated situation since we will handle the char in next loop
                // based on the fact that the format => char(repeatedCount) <=
                repeated = true;
                repeatedCnt = stoi(repStr);
            } else {
                // only char
                int cc;
                if (c == '#') {
                    // i - 2, i - 1, #
                    cc = stoi(encodedString.substr(i - 2, 2));
                    i = i - 3;
                } else {
                    cc = encodedString[i] - '0';
                    i--;
                }

                if (repeated) {
                    repeated = false;
                    res[cc - 1] += repeatedCnt;
                    repeatedCnt = 0;
                } else {
                    res[cc - 1] += 1;
                }
            }
        }
        return res;
    }
};

template <typename T>
void print(std::string_view text, std::vector<T> const &v = {}) {
    std::cout << text << ": ";
    for (const auto &e : v) {
        std::cout << e << ", ";
    }
    std::cout << '\n';
}

int main() {
    Solution s;
    print("Example 1", s.frequency("1226#24#"));
    print("Example 1", s.frequency("23#(2)24#25#26#23#(3)"));
    print("Example 1", s.frequency("2110#(2)"));        // bajj
    print("Example 1", s.frequency("1226#24#"));        // abzx
}

Program: Decode String Frequency Amazon OA Solution in Python

def frequency(s):
    """
    s : 2110#(2)
    """
    # Write your code here
    
    res = [0] * 26
    n = len(s)
    i = n - 1
    while i >= 0:
        cnt = 1
        num = 0
        # if the  
        if s[i] == ')':
            i -= 1
            ts = 0
            while s[i] != '(':
                cnt = int(s[i]) * (10 ** ts)
                ts += 1
                i -= 1
            i -= 1
        if s[i] == '#':
            i -= 2
            num = int(s[i]) * 10 + int(s[i+1])

        if num == 0:
            num = int(s[i])
        
        res[num-1] += cnt
        i -= 1
    print(" ".join(map(str, res)))


if __name__ == '__main__':
    frequency("2110#(2)")
    frequency("1226#24#")
    frequency("23#(2)24#25#26#23#(3)")
    frequency("")
    frequency("10#")

Amazon Online Assessment Questions:

• Robot Bounded in Box
• Number Game
• Find All Combination of Numbers Sum to Target / Shopping Options
• Fill the Truck
• Music Pairs
• Slowest key
• Five Star Seller
• Split String Into Unique Primes
• Storage Optimization
• Minimum Difficulty of a Job Schedule
• Autoscale Policy, Utilization Check
• Optimal Utilization
• Merge Two Sorted Lists
• Two Sum Unique Pairs
• Shopping Patterns
• Reorder Data in Log Files
• Top K Frequent Words
• Trees Height
• Counting Binary Substrings Amazon OA Solution
• Grid Connections Amazon OA Solution
• Shipment Imbalance Amazon OA Solution
• Max Profit Amazon OA Solution
• Find Lowest Price Amazon OA Solution
• Simple Cipher Amazon OA Solution
• Decode String Frequency Amazon OA Solution
• Valid Discount Coupons Amazon OA Solution
• Count Maximum Teams Amazon OA Solution
• Minimum Coin Flips Amazon OA Solution