Apply Discount to Prices
MedPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
This approach breaks the problem down by first splitting the sentence into individual words. Each word is then examined to determine if it's a price. If it is, the discount is applied, and the word is replaced with the newly formatted price. Finally, the words are joined back together to form the complete, modified sentence.
Algorithm
- Split the input
sentencestring into an array of words using the space character as a delimiter. - Create a
StringBuilderto build the resulting sentence. - Iterate through each word in the array.
- For each word, check if it represents a valid price. A word is a price if it starts with '$', has a length greater than 1, and the rest of its characters are digits.
- If the word is a price:
- Extract the numeric part by taking the substring after the '$'.
- Parse this numeric string into a
long. - Calculate the discounted price using the formula:
newValue = originalValue * (1 - discount / 100.0). - Format the new price into a string with a leading '$' and exactly two decimal places (e.g., using
String.format("$%.2f", newValue)). - Append this formatted price string to the
StringBuilder.
- If the word is not a price, append the original word to the
StringBuilder. - Append a space after each word is processed.
- After the loop, remove the trailing space from the
StringBuilderand return the final string.
Walkthrough
The core idea is to use the built-in split() method to easily work with each word. We iterate over the resulting array of words. For each word, a helper function isPrice validates if it matches the price format: starts with '$', has more than one character, and is followed only by digits. If it's a valid price, we parse the numeric value, apply the percentage discount, and format the result to two decimal places. This new string replaces the original word. Non-price words are kept unchanged. A StringBuilder is used to efficiently construct the new sentence by appending each processed word followed by a space.
class Solution { public String applyDiscount(String sentence, int discount) { String[] words = sentence.split(" "); StringBuilder result = new StringBuilder(); double discountFactor = 1 - (discount / 100.0); for (int i = 0; i < words.length; i++) { String word = words[i]; if (isPrice(word)) { long priceValue = Long.parseLong(word.substring(1)); double discountedPrice = priceValue * discountFactor; result.append(String.format("$%.2f", discountedPrice)); } else { result.append(word); } if (i < words.length - 1) { result.append(" "); } } return result.toString(); } private boolean isPrice(String word) { if (word.length() <= 1 || word.charAt(0) != '$') { return false; } for (int i = 1; i < word.length(); i++) { if (!Character.isDigit(word.charAt(i))) { return false; } } return true; }}Complexity
Time
O(N), where N is the length of the sentence. The `split()` operation takes O(N) time. The subsequent loop iterates through the words, and the total work done inside the loop (checking, parsing, formatting) is also proportional to the total length of the sentence.
Space
O(N), where N is the length of the sentence. This is due to the creation of the `words` array from `split()` and the `StringBuilder` for the result, both of which can take space proportional to the input sentence length.
Trade-offs
Pros
The code is straightforward and easy to understand.
It effectively utilizes standard library functions for string manipulation, leading to more concise code.
Cons
Creates an intermediate array of strings when splitting the sentence, which consumes extra memory proportional to the sentence length.
The overhead of splitting the string and then joining the parts can be less performant than a single-pass approach, especially for very long sentences.
This more efficient approach processes the sentence in a single pass without first splitting it into an array. It iterates through the string, identifying words by looking for spaces, and builds the new sentence on the fly. This method reduces memory overhead by avoiding the creation of an intermediate array of words.
Algorithm
- Initialize an empty
StringBuilderto store the result. - Use a pointer
ito iterate through the sentence from the beginning. - In a loop, find the end of the current word, which is marked by the next space or the end of the sentence. Let the end index be
j. - Extract the word using
sentence.substring(i, j). - Check if the extracted word is a valid price (starts with '$', length > 1, followed by digits).
- If it is a price:
- Parse the numeric part to a
long. - Calculate the discounted value.
- Format the result to
"$%.2f". - Append the formatted price to the
StringBuilder.
- Parse the numeric part to a
- If it is not a price, append the original word to the
StringBuilder. - If it's not the last word, append a space to the
StringBuilder. - Update the pointer
itoj + 1to move to the start of the next word. - Continue until the entire sentence is processed and return the
StringBuilder's content.
Walkthrough
Instead of splitting the string, we manually parse it. We use two pointers, or one pointer and indexOf, to find the start and end of each word. A while loop continues as long as we haven't reached the end of the sentence. Inside the loop, we find the next space to determine the current word's boundary. We extract this word and perform the same validation and processing as in the first approach. The processed word (either the discounted price or the original word) is appended to a StringBuilder. This avoids the O(N) space cost of the intermediate array from split(), making it more memory-efficient. The overall time complexity remains the same, but it can be faster in practice due to less overhead.
class Solution { public String applyDiscount(String sentence, int discount) { StringBuilder result = new StringBuilder(); double discountFactor = 1 - (discount / 100.0); int n = sentence.length(); int i = 0; while (i < n) { int j = sentence.indexOf(' ', i); if (j == -1) { // Last word j = n; } String word = sentence.substring(i, j); if (isPrice(word)) { long priceValue = Long.parseLong(word.substring(1)); double discountedPrice = priceValue * discountFactor; result.append(String.format("$%.2f", discountedPrice)); } else { result.append(word); } if (j < n) { result.append(" "); } i = j + 1; } return result.toString(); } private boolean isPrice(String word) { if (word.length() <= 1 || word.charAt(0) != '$') { return false; } for (int k = 1; k < word.length(); k++) { if (!Character.isDigit(word.charAt(k))) { return false; } } return true; }}Complexity
Time
O(N), where N is the length of the sentence. The sentence is traversed once. Operations within the loop like `indexOf` and `substring` contribute to an overall linear time complexity as each character is processed a constant number of times.
Space
O(N) for the `StringBuilder` used to construct the output. This is the optimal space complexity as the output string itself can be of length O(N). It improves upon the first approach by not requiring additional O(N) space for an intermediate array.
Trade-offs
Pros
More memory-efficient as it avoids creating an intermediate array of strings.
Potentially faster due to a single pass over the string and avoiding the overhead associated with the
splitmethod.
Cons
The code involves manual index management, which can be slightly more complex and error-prone than iterating over a pre-split array.
Solutions
Solution
class Solution {public String discountPrices(String sentence, int discount) { String[] words = sentence.split(" "); for (int i = 0; i < words.length; ++i) { if (check(words[i])) { double t = Long.parseLong(words[i].substring(1)) * (1 - discount / 100.0); words[i] = String.format("$%.2f", t); } } return String.join(" ", words); }private boolean check(String s) { if (s.charAt(0) != '$' || s.length() == 1) { return false; } for (int i = 1; i < s.length(); ++i) { if (!Character.isDigit(s.charAt(i))) { return false; } } return true; }}class Solution {public: string discountPrices(string sentence, int discount) { istringstream is(sentence); string w; string ans; auto check = [](string s) { if (s[0] != '$' || s.size() == 1) { return false; } for (int i = 1; i < s.size(); ++i) { if (!isdigit(s[i])) { return false; } } return true; }; while (is >> w) { if (check(w)) { long long v = stoll(w.substr(1)) * (100 - discount); char t[20]; sprintf(t, "$%lld.%02lld", v / 100, v % 100); ans += t; } else { ans += w; } ans += ' '; } ans.pop_back(); return ans; }};class Solution: def discountPrices(self, sentence: str, discount: int) -> str: ans = [] for w in sentence . split(): if w[0] == '$' and w[1:]. isdigit(): w = f '$ { int ( w [ 1 : ]) * ( 1 - discount / 100 ) : . 2 f } ' ans . append(w) return ' ' . join(ans)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.