Page Contents
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 as1
,b
is encoded as2
,c
is encoded as3
, …, andi
is encoded as9
.j
is encoded as10#
,k
is encoded as11#
,l
is encoded as12#
, …, andz
is encoded as26#
.- 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
Not allowing right click is a sad feature and not user friendly at all….
We have disable this feature due to security reasons.