Encoded string algorithm with given rules

Question

Looking for general feedback and if there is a solution that can reduce the time complexity from the current O(n²)? 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 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 a character, then the character count is written within parentheses (i.e., (c), where c 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 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 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;
    }

Answer 1

Returning a List

        List<Integer> freq = new ArrayList<>();
        int[] result = new int[26];

and

        for (int res : result) {
            freq.add(res);
        }
        return freq;

could more easily be written

        Integer[] result = new Integer[26];

and

        return Arrays.toList(result);

Or as already noted, just return the array.

I personally would have named that variable counts instead of result. For one, I name collections and arrays with plural names. For the other, I would find counts more descriptive than results. But as written, this can just drop into your code. I'll use counts in my version.

Read back to front

Your encoding scheme has the optional information afterward. So switch things around and read from the end.

for (int i = s.length() - 1; i > 0; i--) {
    int count = 1;
    if (s.charAt(i) == ')') {
        int last = --i;

        while (s.charAt(i)) != '(') {
            i--;
        }

        count = Integer.parseInt(s.substring(i + 1, last));
        i--;
    }

    int c;
    if (s.charAt(i) == '#') {
        i--;
        c = Integer.parseInt(s.substring(i - 1, i));
        i--;
    } else {
        c = s.charAt(i) - '0';
    }

    counts[c] += count;
}

If we are guaranteed that the input will always be valid, this will correctly parse each group. It first looks for a count, defaulting to 1 if it can't find one. Then it processes the letter encoding. Then it adds the count to the appropriate place. Three simple and separate operations.

As previously noted, if the input is not valid, this version will fail. Your version might be able to survive some invalid inputs that would kill this version. Your version also might return incorrect results for some incorrect inputs. This version is more likely to throw an exception and halt. That may be better than trying to recover, as no results are often better than incorrect results. Or to put this another way, this version is more likely to tell you that something is wrong.

Time complexity

Both your solution and this one are \$\mathcal{O}(n)\$. You may have learned that nested loops are quadratic and that is usually true. But in this case, the inner loop operates on the same loop variable as the outer loop. So it visits each element of the input array once. That's linear on the input size.

Answer 2

Advice 1

List<Integer> freq = new ArrayList<>();

I see no reason why you should pack the result in a ArrayList. Why not return the int[] result instead?

Advice 2

...
int i = 0;
while (i < length) {
    ...

I suggest, for readability, to separate int i = 0; and while (i < length) { with a single empty line:

...
int i = 0;

while (i < length) {
    ...

Same applies to

int val = 0;
if (i + 2 >= length || s.charAt(i + 2) != '#') {

and

}
if (i < length) {

Note 1

Your solution does not check whether the input string is in a valid format. In order to check some of them, you could go as crazy as this:

package com.yourcompany;

import java.util.Arrays;
import java.util.Scanner;

public final class DigitDecoder {

    private static final int NOT_USED = -1;

    public static int[] compute(String s) {
        char[] chars           = s.toCharArray();
        int[] outputArray      = new int[26];
        int currentIndex       = 0;
        char char1             = 0;
        char char2             = 0;
        boolean lastCharIsHash = false;
        boolean readingCount   = false;
        int outputArrayIndex   = NOT_USED;
        int count              = NOT_USED;

        while (currentIndex < chars.length) {
            char c = chars[currentIndex];

            switch (c) {
                case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' -> {
                    if (lastCharIsHash) {
                        if (currentIndex < 2) {
                            throw new IllegalArgumentException(
                                    "Premature '#'.");
                        }

                        lastCharIsHash = false;
                        count = 1;
                        char1 = c;
                        char2 = 0;
                    } else if (readingCount) {
                        // Just append 'c' to the count variable shifting all 
                        // previous digits one position higher:
                        if (count == NOT_USED) {
                            count = 0;
                        }

                        count *= 10;
                        count += c - '0';
                    } else if (char1 == 0) {
                        char1 = c;
                    } else if (char2 == 0) {
                        char2 = c;
                    } else {
                        // Here, we can safely count the 'char1':
                        outputArrayIndex = char1 - '0' - 1;
                        count = 1;
                        char1 = char2;
                        char2 = c;
                    }
                }
                case '#' -> {
                    if (char1 == 0 || char2 == 0) {
                        throw new IllegalArgumentException(
                                "Missing a character at index "
                                        + currentIndex
                                        + ".");
                    }

                    outputArrayIndex = (char1 - '0') * 10 +
                                       (char2 - '0') - 1;

                    lastCharIsHash = true;
                }
                case '(' -> {
                    if (lastCharIsHash) {
                        lastCharIsHash = false;
                    } else if (char2 == 0) {
                        outputArrayIndex = char1 - '0' - 1;
                    } else {
                        outputArray[char1 - '0' - 1]++;
                        outputArrayIndex = char2 - '0' - 1;
                    }

                    if (currentIndex == 0) {
                        throw new IllegalArgumentException(
                                "'(' cannot be the first characters.");
                    }

                    if (currentIndex > chars.length - 3) {
                        throw new IllegalArgumentException("No closing ')'.");
                    }

                    readingCount = true;
                }
                case ')' -> {
                    if (char2 == 0) {
                        if (char1 == 0) {
                            return outputArray;
                        } else {
                            outputArrayIndex = char1 - '0' - 1;
                        }
                    } else {
                        // Here, char2 not zero:
                        if (char1 == 0) {
                            throw new IllegalArgumentException(
                                    "Should not get here.");
                        }
                    }

                    char1 = 0;
                    char2 = 0;
                    readingCount = false;
                }
                default -> throw new IllegalArgumentException(
                        "Unknown character: " + c);
            }

            currentIndex++;

            if (!readingCount 
                    && outputArrayIndex != NOT_USED 
                    && count != NOT_USED) {
                outputArray[outputArrayIndex] += count;
                outputArrayIndex = NOT_USED;
                count = NOT_USED;
            }
        }

        // Discharge the character buffer leftovers:
        if (char2 != 0) {
            if (char1 == 0) {
                throw new IllegalStateException(
                        "Missing first character in the buffer.");
            }

            // Once here, both the digits are in the buffer:
            if (lastCharIsHash) {
                int index = (char1 - '0') * 10 + char2 - '0' - 1;
                outputArray[index]++;
            } else {
                int index1 = char1 - '0' - 1;
                int index2 = char2 - '0' - 1;
                outputArray[index1]++;
                outputArray[index2]++;
            }
        } else if (char1 != 0) {
            // Only first character in the buffer left:
            outputArray[char1 - '0' - 1]++;
        }

        return outputArray;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] decodedInts1 = null;
        int[] decodedInts2 = null;

        while (true) {
            String code = scanner.nextLine();

            if (code.trim().equals("q")) {
                System.out.println("Bye!");
                return;
            }

            boolean noCompare = false;

            try {
                decodedInts1 = compute(code);
                System.out.println("cr: " + Arrays.toString(decodedInts1));
            } catch (Throwable t) {
                System.err.println(
                        "coderodde's implementation failed: " 
                                + t.getMessage() + ".");

                noCompare = true;
            }

            try {
                decodedInts2 = OPDigitDecoder.frequency(code);
                System.out.println("OP: " + Arrays.toString(decodedInts2));
            } catch (Throwable t) {
                System.err.println(
                        "OP's implementation failed: " 
                                + t.getMessage() + ".");

                noCompare = true;
            }

            if (!noCompare) {
                System.out.println(
                        "Algorithms agree: " 
                                + Arrays.equals(decodedInts1, decodedInts2));
            }
        }
    }
}

(The unit tests comparing your and mine solutions live here.)