# Decode String Frequency Amazon OA Solution

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 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. Decode String Frequency Amazon OA Solution

## 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 =  * 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:

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

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

• 