Compute letter frequencies from encoded string
Company: Oracle
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
You are given an encoded string `s` representing a string of lowercase English letters (`a`–`z`). The encoding follows these rules:
1. Letters `a` to `i` are encoded as digits `1` to `9`.
- `a -> "1"`, `b -> "2"`, …, `i -> "9"`
2. Letters `j` to `z` are encoded as two digits followed by `#`.
- `j -> "10#"`, `k -> "11#"`, …, `z -> "26#"`
3. If a letter repeats **consecutively** `k >= 2` times, the repetition is encoded by appending `"(k)"` immediately after that letter’s code.
- Example: `"aa" -> "1(2)"`, `"ccc" -> "3(3)"`, `"jj" -> "10#(2)"`
### Task
Return an integer array `counts` of length 26, where `counts[0]` is the number of `'a'` characters in the decoded string, `counts[1]` is the number of `'b'`, …, and `counts[25]` is the number of `'z'`.
### Examples
- `s = "1226#24#"` decodes to `"abzx"`.
- `s = "1(2)23(3)"` decodes to `"aabccc"`.
- `s = "2110#(2)"` decodes to `"bajj"`.
- `s = "23#(2)24#25#26#23#(3)"` decodes to `"wwxyzwww"`.
### Input/Output
- **Input:** a string `s` consisting of digits, `#`, `(`, and `)` that follows the encoding rules above.
- **Output:** an array of 26 integers with letter frequencies.
### Notes / Constraints (reasonable interview assumptions)
- `s` is validly encoded.
- Counts in parentheses can be multiple digits (e.g., `(12)`).
- Aim for `O(|s|)` time and `O(1)` extra space (excluding the output array).
Overview: This question evaluates proficiency in string parsing and frequency aggregation, specifically handling mixed-length encodings, tokenization of digits and '#' markers, and parsing numeric repetition counts while respecting linear-time and constant-space constraints.
You are given an encoded string `s` representing a string of lowercase English letters (`a`-`z`). The encoding follows these rules:
1. Letters `a` to `i` are encoded as digits `1` to `9` (`a -> "1"`, `b -> "2"`, ..., `i -> "9"`).
2. Letters `j` to `z` are encoded as two digits followed by `#` (`j -> "10#"`, `k -> "11#"`, ..., `z -> "26#"`).
3. If a letter repeats **consecutively** `k >= 2` times, the repetition is encoded by appending `"(k)"` immediately after that letter's code (`"aa" -> "1(2)"`, `"ccc" -> "3(3)"`, `"jj" -> "10#(2)"`).
**Task:** Return an integer array `counts` of length 26, where `counts[0]` is the number of `'a'` characters in the decoded string, `counts[1]` is the number of `'b'`, ..., and `counts[25]` is the number of `'z'`.
**Examples**
- `s = "1226#24#"` decodes to `"abzx"`.
- `s = "1(2)23(3)"` decodes to `"aabccc"`.
- `s = "2110#(2)"` decodes to `"bajj"`.
- `s = "23#(2)24#25#26#23#(3)"` decodes to `"wwxyzwww"`.
**Notes / Constraints**
- `s` is validly encoded.
- Counts in parentheses can be multiple digits (e.g., `(12)`).
- Aim for `O(|s|)` time and `O(1)` extra space (excluding the output array).
Constraints
- s is a valid encoding produced by the rules above.
- Single-letter codes are 1..9 (a..i); two-letter codes are 10#..26# (j..z).
- A repetition suffix (k) appears only after a letter code, with k >= 2; k may have multiple digits.
- Output is exactly 26 integers, index 0 = 'a' through index 25 = 'z'.
Examples
Input: ("1226#24#",)
Expected Output: [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1]
Explanation: Decodes to "abzx": 1->a, 2->b, 26#->z, 24#->x.
Input: ("1(2)23(3)",)
Expected Output: [2, 1, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Explanation: Decodes to "aabccc": 1(2)->aa, 2->b, 3(3)->ccc.
Hints
- Scan left to right. The only way to tell a two-digit letter (10#..26#) from a single digit is to peek two characters ahead for a '#'.
- After consuming a letter's code, check whether the next character is '('. If so, read the integer up to ')' — it can be more than one digit — and use it as the multiplier; otherwise the letter occurs once.
- Map the numeric value v (1..26) to array index v-1 and add the repetition count there.
Community answers
Answer by thedevunit
package Solution;
import java.util.Arrays;
public class DecodeCounts {
public static int[] decodeCounts(String s) {
int[] counts = new int[26];
int n = s.length();
int i = 0;
while (i < n) {
int letterIdx;
// Two-digit letter iff a '#' sits two chars ahead (pattern: d d #).
if (i + 2 < n && s.charAt(i + 2) == '#') {
int num = (s.charAt(i) - '0') * 10 + (s.charAt(i + 1) - '0');
letterIdx = num - 1; // 10..26 -> 9..25 (j..z)
i += 3; // skip "dd#"
} else {
letterIdx = s.charAt(i) - '1'; // 1..9 -> 0..8 (a..i)
i += 1;
}
// Optional repetition "(k)", where k can be multi-digit.
int count = 1;
if (i < n && s.charAt(i) == '(') {
i++; // skip '('
count = 0;
while (s.charAt(i) != ')') {
count = count * 10 + (s.charAt(i) - '0');
i++;
}
i++; // skip ')'
}
counts[letterIdx] += count;
}
return counts;
}
// Helper: rebuild the decoded string so we can eyeball correctness.
private static String render(int[] counts) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 26; i++) {
for (int c = 0; c < counts[i]; c++) {
sb.append((char) ('a' + i));
}
}
return sb.toString();
}
// Helper: print only the non-zero buckets.
private static String nonZero(int[] counts) {
StringBuilder sb = new StringBuilder("{");
for (int i = 0; i < 26; i++) {
if (counts[i] > 0) {
if (sb.length() > 1) sb.append(", ");
sb.append((char) ('a' + i)).append("=").append(counts[i]);
}
}
return sb.append("}").toString();
}
// Frequency array of the expected decoded string — order-independent.
private static int[] freq