Goal Parser Interpretation

Easy
224.

Goal Parser Interpretation

Goal Parser Interpretation is an easy coding problem on strings, asked in Amazon and Adobe interviews.

You own a Goal Parser that reads a string made only of "G", "()" and "(al)". It interprets "G" as "G", "()" as "o" and "(al)" as "al", then concatenates the pieces in order.

Given the string command, return the parser's interpretation.

Example 1

Input
command = "G()(al)"
Output
Goal

Example 2

Input
command = "G()()()()(al)"
Output
Gooooal

Example 3

Input
command = "(al)G(al)()()G"
Output
alGalooG

Constraints

  • 1 <= command.length <= 40
  • command consists only of "G", "()" and "(al)" in some order.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} command
 * @return {string}
 */
var interpret = function(command) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Goal Parser Interpretation — Solution in Python, Java & C++

Goal Parser Interpretation solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on strings.

Goal Parser Interpretation is an easy coding problem on strings, asked in Amazon and Adobe interviews.

  • Difficulty: Easy
  • Topics: Strings
  • Asked at: Amazon, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You own a Goal Parser that reads a string made only of "G", "()" and "(al)". It interprets "G" as "G", "()" as "o" and "(al)" as "al", then concatenates the pieces in order.

Given the string command, return the parser's interpretation.

Example 1

Input: command = "G()(al)"
Output: Goal

Example 2

Input: command = "G()()()()(al)"
Output: Gooooal

Example 3

Input: command = "(al)G(al)()()G"
Output: alGalooG

Constraints

  • 1 <= command.length <= 40
  • command consists only of "G", "()" and "(al)" in some order.

Hints for Goal Parser Interpretation

  1. Hint 1

    Scan left to right; the character at the cursor tells you which of the three tokens starts there.

  2. Hint 2

    A G advances one, () advances two, (al) advances four.

  3. Hint 3

    Peeking at the next character after a ( is enough to tell () from (al).

How to solve Goal Parser Interpretation

The three tokens never overlap, so two ordered substitutions — () → o, then (al) → al — produce the interpretation.

Approach

  1. Replace every () with o.
  2. Replace every (al) with al.
  3. Return the result (the Gs are unchanged).

Why it works

() and (al) cannot share characters in a valid command, and replacing () first never creates or destroys an (al). A left-to-right scan that inspects the character after each ( is the equivalent single-pass form.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Swapping the order of the two replacements is still safe here; the danger would be a replacement that produces a (.

Reference solution

Python

def interpret(command: str) -> str:
    return command.replace("()", "o").replace("(al)", "al")

Java

public static String interpret(String command) {
    StringBuilder out = new StringBuilder();
    int i = 0;
    while (i < command.length()) {
        if (command.charAt(i) == 'G') {
            out.append('G');
            i += 1;
        } else if (command.charAt(i + 1) == ')') {
            out.append('o');
            i += 2;
        } else {
            out.append("al");
            i += 4;
        }
    }
    return out.toString();
}

C++

string interpret(string command) {
    string out = "";
    int i = 0;
    int n = (int) command.size();
    while (i < n) {
        if (command[i] == 'G') { out += 'G'; i += 1; }
        else if (command[i + 1] == ')') { out += 'o'; i += 2; }
        else { out += "al"; i += 4; }
    }
    return out;
}

JavaScript

var interpret = function(command) {
    let out = "";
    let i = 0;
    while (i < command.length) {
        if (command[i] === "G") { out += "G"; i += 1; }
        else if (command[i + 1] === ")") { out += "o"; i += 2; }
        else { out += "al"; i += 4; }
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings