Encoded Message Frequency

Moderate
0/80
0 upvote
Asked in company
Amazon

Problem statement

You are given a string encoded with a special algorithm. Your task is to decode the string and count the frequency of each letter from 'A' to 'Z' in the final decoded message.


The encoding rules are as follows:

  • Single-Digit Characters: The letters 'A' through 'I' are represented by the digits 1 through 9 respectively.
  • Double-Digit Characters: The letters 'J' through 'Z' are represented by two digits (10 through 26) followed by a # symbol. For example, 10# is 'J', 11# is 'K', and so on.
  • Repetition: A character or character sequence can be followed by a repetition marker in the format [k], where k is an integer. This means the character decoded just before the [ appears k times. For example, 1[3] decodes to three 'A's, and 12#[2] decodes to two 'L's.

    Your function should not return the full decoded string (which could be very long). Instead, it must return an array or list of 26 integers, where the element at index 0 is the frequency of 'A', at index 1 is the frequency of 'B', and so on.


Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first and only line of input contains the encoded string s.


Output Format: 
Your function should return a list/array of 26 integers. The runner code will handle printing these integers separated by spaces.


Notes: 
The key to solving this efficiently is to parse the string without actually constructing the fully decoded string. Iterate through the encoded string, decode one character representation at a time, check for an optional repetition block, and update a frequency array directly.
Sample Input 1:
1[3]12#2[4]


Sample Output 1:
3 4 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0


Explanation for Sample 1:
1[3]: The digit 1 represents 'A'. It is followed by [3], so the count of 'A' is 3.
12#: The number 12 followed by # represents 'L'. There is no repetition block, so the count of 'L' is 1.
2[4]: The digit 2 represents 'B'. It is followed by [4], so the count of 'B' is 4.
Final Frequencies: 'A': 3, 'B': 4, 'L': 1. The output array shows these counts at their respective positions.


Expected Time Complexity:
The expected time complexity is O(N).


Constraints:
1 <= length of s <= 2000
1 <= k (in [k]) <= 1000
The input string is guaranteed to be well-formed according to the rules.
Time Limit: 1 sec
Approaches (1)
Brute Force
Time Complexity
Space Complexity
Code Solution
(100% EXP penalty)
Encoded Message Frequency
Full screen
Console