Apply Discount to Prices - Solution & Explanation
Problem Statement
A sentence is a string of single-space separated words where each word can contain digits, lowercase letters, and the dollar sign '$'. A word represents a price if it is a sequence of digits preceded by a dollar sign.
- For example,
"$100","$23", and"$6"represent prices while"100","$", and"$1e5"do not.
You are given a string sentence representing a sentence and an integer discount. For each word representing a price, apply a discount of discount% on the price and update the word in the sentence. All updated prices should be represented with exactly two decimal places.
Return a string representing the modified sentence.
Note that all prices will contain at most 10 digits.
Example 1:
Input: sentence = "there are $1 $2 and 5$ candies in the shop", discount = 50 Output: "there are $0.50 $1.00 and 5$ candies in the shop" Explanation: The words which represent prices are "$1" and "$2". - A 50% discount on "$1" yields "$0.50", so "$1" is replaced by "$0.50". - A 50% discount on "$2" yields "$1". Since we need to have exactly 2 decimal places after a price, we replace "$2" with "$1.00".
Example 2:
Input: sentence = "1 2 $3 4 $5 $6 7 8$ $9 $10$", discount = 100 Output: "1 2 $0.00 4 $0.00 $0.00 7 8$ $0.00 $10$" Explanation: Applying a 100% discount on any price will result in 0. The words representing prices are "$3", "$5", "$6", and "$9". Each of them is replaced by "$0.00".
Constraints:
1 <= sentence.length <= 105sentenceconsists of lowercase English letters, digits,' ', and'$'.sentencedoes not have leading or trailing spaces.- All words in
sentenceare separated by a single space. - All prices will be positive numbers without leading zeros.
- All prices will have at most
10digits. 0 <= discount <= 100
Approach Overview
Problem Overview: You receive a sentence containing words separated by spaces. Some words represent prices that start with $ followed by digits. Apply a given percentage discount to those prices and return the updated sentence with each discounted value formatted to two decimal places.
Approach 1: Iterative Approach Using Split and Join (O(n) time, O(n) space)
Split the sentence into tokens using spaces. Iterate through each word and check whether it represents a valid price. A valid price starts with $ and the remaining characters are digits only. When a valid token is found, convert the numeric portion to a number, apply the discount using price * (100 - discount) / 100, and format the result to two decimal places. Replace the token with the discounted value and finally join all tokens back into a sentence. This approach relies on straightforward string processing and explicit validation logic.
The key insight is strict validation: tokens like $100 are valid, but $100a, $, or 100$ are not. Checking characters with digit validation ensures only legitimate price values are modified. Since each character in the sentence is processed once during splitting and validation, the time complexity is O(n), where n is the sentence length.
Approach 2: Regex and String Manipulation (O(n) time, O(n) space)
This approach uses a regular expression to detect valid price patterns directly. A pattern like \$[0-9]+ identifies words beginning with $ followed strictly by digits. After locating matches, extract the numeric portion, compute the discounted value, and replace the match with the formatted result.
Regex reduces manual validation logic and makes the pattern definition explicit. The algorithm scans the string once while applying replacements, which keeps the time complexity at O(n). This method is common when working with structured text and regular expressions. It pairs well with languages like C++ or Java that provide efficient regex utilities.
Recommended for interviews: The split-and-iterate approach is usually preferred in interviews. It shows you can validate tokens, manipulate string data, and control formatting without relying on heavy libraries. The regex solution is concise and practical for production code but may hide some of the logic interviewers want to see. Demonstrating the iterative validation first, then mentioning regex as an alternative, shows both algorithmic clarity and real-world engineering judgment.
Approach 1: Iterative Approach Using Split and Join
This approach involves iterating through each word in the sentence, checking if it represents a price, and then applying the discount if it does.
Here's a step-by-step breakdown:
- Split the original sentence into an array of words using spaces as delimiters.
- Iterate through each word to check if it starts with the symbol '$' followed by digits.
- If a word is identified as a price, convert the numeric portion to a float, apply the discount, and format it to two decimal points.
- Replace the original price in the array with the newly computed price.
- Join the words back into a string to return the updated sentence.
The function 'apply_discount' takes a sentence and a discount as input. It splits the sentence into words, checks each word to see if it's a price, applies the discount, and replaces the price in the list with the updated value. Finally, it joins the words back into a sentence.
Code
Python
JavaScript
Complexity
Time Complexity: O(n) - where n is the length of the sentence since we iterate over each character once.
Space Complexity: O(n) - for storing words in the list.
Approach 2: Regex and String Manipulation
This approach uses regular expressions to identify price patterns within the sentence.
Steps:
- Utilize regular expressions to search for patterns that match prices, i.e., start with '$' and followed by digits.
- For each match, compute the new price by applying the discount, ensuring it’s correctly formatted to two decimal places.
- Replace the original price with the discounted price in the sentence.
The C++ solution uses std::regex to find instances of prices, calculates the new price using the discount, formats it to two decimal places, and builds a new string with the updated prices.
Complexity
Time Complexity: O(n * m) - where n is the length of the sentence and m is the approximate number of price matches.
Space Complexity: O(n) - for the result string copy.
Approach 3: Simulation
We can split the sentence into an array of words by spaces, then iterate through the array of words. For each word, if it represents a price, we update it to the price after applying the discount. Finally, we concatenate the updated array of words into a space-separated string.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string sentence.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Iterative Approach Using Split and Join | Time Complexity: O(n) - where n is the length of the sentence since we iterate over each character once. |
| Regex and String Manipulation | Time Complexity: O(n * m) - where n is the length of the sentence and m is the approximate number of price matches. |
| Simulation | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Split and Join | O(n) | O(n) | Best for interviews and clear token validation logic |
| Regex and String Manipulation | O(n) | O(n) | When pattern matching tools are available and concise code is preferred |
Video Solution
Apply Discount to Prices | Leetcode 2289 | Maps | Contest 295 🔥🔥 • Coding Decoded • 1,783 views views
Watch 5 more video solutions →Frequently Asked Questions
Is Apply Discount to Prices easy or hard?
Apply Discount to Prices Python/Java solution
How to solve Apply Discount to Prices in O(n)?
What is the best approach for Apply Discount to Prices?
Is Apply Discount to Prices asked at Google/Amazon/Meta?
What data structure is used in Apply Discount to Prices?
What is the time complexity of Apply Discount to Prices?
Ready to solve this problem?
Practice Apply Discount to Prices with our built-in code editor and test cases.
Practice on FleetCode