# Decode String Frequency Amazon OA 2023

## Decode String Frequency Amazon OA 2023 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)
"""

res =  * 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 OA 2023 Questions with Solution

### 2 thoughts on “Decode String Frequency Amazon OA 2023”

1. Not allowing right click is a sad feature and not user friendly at all….

• We have disable this feature due to security reasons.