Goal Parser Interpretation - Practice Coding Problems

Goal Parser Interpretation - Problem

String Easy

You own a Goal Parser that can interpret a string command. The command consists of an alphabet of "G", "()" and/or "(al)" in some order.

The Goal Parser will interpret:

"G" as the string "G"
"()" as the string "o"
"(al)" as the string "al"

The interpreted strings are then concatenated in the original order.

Given the string command, return the Goal Parser's interpretation of command.

Input & Output

Example 1 — Basic Mixed Command

$ Input: command = "G()(al)"

› Output: "Goal"

💡 Note: G stays G, () becomes o, (al) becomes al. Concatenated: G + o + al = "Goal"

Example 2 — Multiple Patterns

$ Input: command = "G()()()()(al)"

› Output: "Goooal"

💡 Note: G stays G, each () becomes o (4 times), (al) becomes al. Result: G + o + o + o + o + al = "Goooal"

Example 3 — Only Parentheses

$ Input: command = "(al)G(al)()()G"

› Output: "alGalooG"

💡 Note: (al)→al, G→G, (al)→al, ()→o, ()→o, G→G. Concatenated: "alGalooG"

Constraints

1 ≤ command.length ≤ 100
command consists of "G", "()", and/or "(al)" in some order

Visualization

Tap to expand

Understanding the Visualization

Input Command

String with G, (), and (al) tokens

Token Mapping

G→G, ()→o, (al)→al

Concatenate

Join decoded tokens into final string

Key Takeaway

🎯 Key Insight: Simple token replacement - scan and decode each pattern G, (), (al) then concatenate

Asked in

a Amazon 15 M Microsoft 12 G Google 8

The key insight is simple pattern replacement. We can either parse character-by-character or use string replacement. The optimal approach uses built-in string replace functions for cleaner code. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Character-by-Character Parsing	O(n)	O(n)	Iterate through string and decode each token manually
String Replacement	O(n)	O(n)	Use built-in string replace functions to decode patterns

Character-by-Character Parsing — Algorithm Steps

Iterate through each character in the command
If character is 'G', append 'G' to result
If character is '(', check next characters to determine '()' or '(al)'
Append corresponding decoded string and skip processed characters

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan

Check each character from left to right

Decode

Convert G, (), (al) to their meanings

Build

Concatenate decoded parts

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* solution(char* command) {
    int len = strlen(command);
    char* result = (char*)malloc((len + 1) * sizeof(char));
    int j = 0;
    int i = 0;
    
    while (i < len) {
        if (command[i] == 'G') {
            result[j++] = 'G';
            i++;
        } else if (command[i] == '(') {
            if (i + 1 < len && command[i + 1] == ')') {
                result[j++] = 'o';
                i += 2;
            } else {  // command[i:i+4] == "(al)"
                result[j++] = 'a';
                result[j++] = 'l';
                i += 4;
            }
        }
    }
    
    result[j] = '\0';
    return result;
}

int main() {
    char command[101];
    fgets(command, sizeof(command), stdin);
    command[strcspn(command, "\n")] = 0;
    
    char* result = solution(command);
    printf("%s\n", result);
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the string, each character processed once

✓ Linear Growth

Space Complexity

O(n)

Result string stores decoded output up to n characters

⚡ Linearithmic Space

29.4K Views

Medium Frequency

~5 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Character-by-Character Parsing — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler