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", and "(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.
Example 1:
Input: command = "G()(al)" Output: "Goal" Explanation: The Goal Parser interprets the command as follows: G -> G () -> o (al) -> al The final concatenated result is "Goal".
Example 2:
Input: command = "G()()()()(al)" Output: "Gooooal"
Example 3:
Input: command = "(al)G(al)()()G" Output: "alGalooG"
Constraints:
1 <= command.length <= 100command consists of "G", "()", and/or "(al)" in some order.The problem asks you to interpret a command string following simple parsing rules: "G" remains "G", "()" becomes "o", and "(al)" becomes "al". The key idea is to scan the string from left to right and build the interpreted result step by step.
A common approach is to use a pointer or index to iterate through the string. When you encounter 'G', append it directly to the result. If you see an opening parenthesis, check the next characters to determine whether the pattern is () or (al), then append the corresponding output. This is essentially a simple pattern-matching or parsing task.
Because each character is processed at most once, the algorithm runs efficiently. The result can be constructed using a string builder or similar structure for optimal performance.
Time Complexity: O(n), where n is the length of the command string. Space Complexity: O(n) for the output string.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Single Pass String Parsing | O(n) | O(n) |
| Pattern Replacement / String Builder | O(n) | O(n) |
ProjectNinjaTech
Use these hints if you're stuck. Try solving on your own first.
You need to check at most 2 characters to determine which character comes next.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
While this exact problem may not always appear, similar string parsing and pattern interpretation problems are common in technical interviews. It helps test your ability to process strings and recognize patterns efficiently.
A string builder or dynamic string structure is ideal for constructing the result efficiently. It allows characters and substrings to be appended without creating multiple intermediate strings.
The optimal approach is a single-pass string parsing method. Iterate through the command string and translate patterns like "G", "()", and "(al)" as you encounter them. This ensures linear time processing and avoids unnecessary re-scanning.
Yes, you can solve it using built-in string replacement methods by replacing "()" with "o" and "(al)" with "al". However, interviewers often prefer a manual parsing approach to demonstrate understanding of string traversal.