Looking for general feedback and if there is a solution that can reduce the time complexity from the current O(n2)? Thank you.
Problem Statement
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 a character, then the character count is written within parentheses (i.e.,
(c)
, wherec
is an integer denoting count of consecutive occurrences being encoded) immediately following the encoded character. For example, consider the following string encodings:- String
abzx
is encoded ass = 1226#24#
. - String
aabccc
is encoded ass = 1(2)23(3)
. - String
bajj
is encoded ass = 2110#(2)
. - String
wwxyzwww
is encoded ass = 23#(2)24#25#26#23#(3)
.
- String
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 b
characters and so on.
Test cases
Example 1
- Input:
"1(2)23(3)"
- 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]
Example 2
- Input:
"2110#(2)"
- Output:
[1, 1, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Example 3
- Input:
"1226#24#"
- 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]
My Solution
public static List<Integer> frequency(String s) {
List<Integer> freq = new ArrayList<>();
int[] result = new int[26];
int length = s.length();
int i = 0;
while (i < length) {
int val = 0;
if (i + 2 >= length || s.charAt(i + 2) != '#') {
val = s.charAt(i) - '0';
result[val - 1]++;
i++;
} else if (s.charAt(i + 2) == '#') {
val = (s.charAt(i) - '0') * 10 + (s.charAt(i + 1) - '0');
result[val - 1]++;
i = i + 3;
}
if (i < length) {
if (s.charAt(i) == '(') {
int fr = 0;
i++;
while (s.charAt(i) != ')') {
fr = fr * 10 + (s.charAt(i) - '0');
i++;
}
result[val - 1] += fr - 1;
i++;
}
}
}
for (int res : result) {
freq.add(res);
}
return freq;
}
frequency()
? \$\endgroup\$