Decoding Recipe Ingredients — Problem Statement & Solution Guide
Problem Description
You are given a single string s that contains a sequence of ingredient names and their quantities. Each ingredient name consists of lowercase English letters and is immediately followed by a positive integer representing its quantity. There are no delimiters between consecutive ingredient-quantity pairs. Your task is to parse s and return an array of pairs, where each pair contains the ingredient name and its quantity as an integer, preserving the original order.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Decoding Recipe Ingredients"
WHY DOES IT MATTER?
The alternating pattern of letters and digits is a classic example of a tokenization problem where a single-pass DFA yields optimal performance. It eliminates the need for expensive regular expression matching or repeated substring extraction, which would otherwise dominate the runtime.
OPTIMIZATION CHALLENGE
The key insight is that the boundary between a name and a quantity is determined solely by the character type—letter vs. digit. Recognizing this allows us to process each character once, avoiding backtracking or lookahead.
REAL-WORLD CONNECTION
Consider parsing log files where timestamps (digits) alternate with log levels (letters). A single-pass scanner that switches between collecting characters and numbers is used in high-throughput log ingestion pipelines to keep latency low.
When explaining this to an interviewer, emphasize the state machine: state 0 collects letters, state 1 collects digits. Show how you transition on encountering a digit, parse the number, reset the buffer, and continue. This demonstrates clear thinking and mastery of linear parsing.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The problem reduces to parsing a concatenated string of alternating alphabetic ingredient names and numeric quantities. A naive approach would attempt to split the string at every possible boundary, leading to exponential time as each character could be interpreted as either part of a name or a number. The optimal solution leverages a single linear scan: iterate through the string, accumulate consecutive letters into a buffer until a digit is encountered, then parse the following digits as an integer. This greedy, stateful traversal guarantees O(n) time and O(n) space for the result, where n is the length of the input string. The underlying algorithmic pattern is a deterministic finite automaton (DFA) that alternates between two states—collecting letters and collecting digits—ensuring each character is processed exactly once.
This linear-time strategy is essential for large inputs because the input string can be millions of characters long in real-world scenarios such as batch processing of ingredient lists from e-commerce platforms. By avoiding nested loops or repeated substring operations, we keep both time and memory usage within practical limits, making the solution scalable and production-ready.
Interview Questions on This Problem
Q1How would you handle an input string that contains uppercase letters or special characters in the ingredient names?
The problem statement guarantees lowercase letters only, but in a real interview you should clarify assumptions. If uppercase or special characters were allowed, you would adjust the letter-collecting logic to accept those characters, perhaps by using a regex or a character class that includes them. The core algorithm—stateful scanning—remains unchanged.
Q2Can you modify the algorithm to also return the total quantity of all ingredients?
Yes. While parsing, maintain a running sum of the parsed integers. After the scan, return both the array of pairs and the sum. This adds O(1) extra space and O(n) time, preserving the overall complexity.
Q3What if the input string could have leading zeros in the quantity? How would you parse them?
Leading zeros are acceptable in integer parsing; you can use a standard integer conversion that ignores them, such as parseInt in JavaScript or Integer.parseInt in Java. If you need to preserve the exact string representation, store the numeric substring as-is and convert only when necessary.
Examples
Input
sugar10flour200milk5
Output
[["sugar",10],["flour",200],["milk",5]]
Explanation: Start at the beginning of the string. Read letters until a digit is encountered: "sugar". The following digits form the quantity 10. Record the pair ["sugar",10]. Continue from the next character: "flour" followed by 200. Record ["flour",200]. Finally read "milk" and 5, record ["milk",5]. The resulting array preserves the order of appearance.
Input
egg2butter3milk1
Output
[["egg",2],["butter",3],["milk",1]]
Explanation: Read letters until a digit: "egg" → quantity 2. Next letters: "butter" → quantity 3. Finally "milk" → quantity 1. Assemble the pairs in the same order.
Constraints
- 1 <= length of input string <= 100
- Ingredient quantities are between 1 and 9
Optimal Approach & Strategy
The optimal approach scans the string once, using two buffers: one for letters and one for digits. When a transition from letters to digits occurs, parse the digits as an integer, pair it with the accumulated letters, and reset the buffers. This yields linear time and linear space.
Brute Force Approach
A naive solution would try every possible split point, treating each prefix as a potential ingredient name and the rest as quantity, leading to exponential time. It would also repeatedly create substrings, causing high memory usage.
Verified Code Solutions
/**
* @param {string} s
* @return {string[][]}
*/
var decodeRecipe = function(s) {
const result = [];
let i = 0;
while (i < s.length) {
let start = i;
while (i < s.length && /[a-z]/.test(s[i])) {
i++;
}
const name = s.substring(start, i);
let numStart = i;
while (i < s.length && /[0-9]/.test(s[i])) {
i++;
}
const quantity = parseInt(s.substring(numStart, i), 10);
result.push([name, quantity]);
}
return result;
};class Solution {
public:
vector<vector<string>> decodeRecipe(string s) {
vector<vector<string>> result;
int n = s.length();
int i = 0;
while (i < n) {
int start = i;
while (i < n && isalpha(s[i])) {
i++;
}
string name = s.substr(start, i - start);
int numStart = i;
while (i < n && isdigit(s[i])) {
i++;
}
string numStr = s.substr(numStart, i - numStart);
int quantity = stoi(numStr);
vector<string> pair;
pair.push_back(name);
pair.push_back(to_string(quantity));
result.push_back(pair);
}
return result;
}
};class Solution {
public List<List<String>> decodeRecipe(String s) {
List<List<String>> result = new ArrayList<>();
int n = s.length();
int i = 0;
while (i < n) {
int start = i;
while (i < n && Character.isLetter(s.charAt(i))) {
i++;
}
String name = s.substring(start, i);
int numStart = i;
while (i < n && Character.isDigit(s.charAt(i))) {
i++;
}
int quantity = Integer.parseInt(s.substring(numStart, i));
List<String> pair = new ArrayList<>();
pair.add(name);
pair.add(String.valueOf(quantity));
result.add(pair);
}
return result;
}
}class Solution:
def decodeRecipe(self, s: str) -> List[List[str]]:
result = []
i = 0
n = len(s)
while i < n:
start = i
while i < n and s[i].isalpha():
i += 1
name = s[start:i]
num_start = i
while i < n and s[i].isdigit():
i += 1
quantity = int(s[num_start:i])
result.append([name, quantity])
return result/**
* @param {string} s
* @return {string[][]}
*/
var decodeRecipe = function(s) {
const result = [];
let i = 0;
while (i < s.length) {
let start = i;
while (i < s.length && /[a-z]/.test(s[i])) {
i++;
}
const name = s.substring(start, i);
let numStart = i;
while (i < s.length && /[0-9]/.test(s[i])) {
i++;
}
const quantity = parseInt(s.substring(numStart, i), 10);
result.push([name, quantity]);
}
return result;
};Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.