LeetCode 2288 - Apply Discount to Prices

Difficulty: 🟡 Medium
Topics: String

Solution

Problem Understanding

The problem asks us to process a string representing a sentence containing words and prices, where prices are words that start with a dollar sign $ followed by digits. The task is to apply a given percentage discount to every price in the sentence and update the sentence with the discounted prices formatted with exactly two decimal places. Non-price words and malformed price-like words (e.g., $1e5 or 5$) should remain unchanged.

The input sentence is guaranteed to have single-space-separated words with no leading or trailing spaces, and all valid prices are positive integers without leading zeros and at most 10 digits long. The discount value ranges from 0 to 100. The main challenge is correctly identifying valid prices and ensuring precise formatting after applying the discount, especially for cases like rounding to exactly two decimal places or applying a 100% discount.

Important edge cases include words that start with $ but contain letters or extra symbols, words that end with $, very large prices close to 10 digits, a 0% discount (no change), and a 100% discount (price becomes $0.00).

Approaches

A brute-force approach would iterate over each word, check if it starts with $, attempt to parse the substring as an integer, and if parsing succeeds, compute the discounted price and format it with two decimals. This works correctly but can be made more concise and efficient by using Python string and number formatting facilities without manual parsing and string concatenation logic.

The key insight for the optimal solution is that valid prices strictly follow the $ followed by digits pattern. By splitting the sentence into words, checking each word against this pattern, converting the numeric part to a float, applying the discount, and formatting it back to two decimals, we can process the entire sentence efficiently in a single pass without extra data structures.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n*m)	O(n)	Split sentence into words, parse each word with conditional checks, compute discount, reassemble sentence
Optimal	O(n)	O(n)	Single pass split, check numeric pattern, compute discounted price with formatting, reconstruct sentence

Here n is the number of characters in the sentence, and m is the average word length.

Algorithm Walkthrough

Split the input sentence into words using the space character as a delimiter. This allows us to process each word independently and reconstruct the sentence later.
Iterate over each word. For each word:

a. Check if it starts with $ and has more than one character.

b. Verify that all characters after the $ are digits. If not, treat it as a non-price word.

c. Convert the numeric portion into a float.

d. Compute the discounted price as price * (100 - discount) / 100.

e. Format the discounted price as a string with exactly two decimal places prefixed by $. 3. Replace the original word in the sentence with the discounted price if it is valid, otherwise keep it unchanged. 4. Join all words back into a single string with spaces to form the final modified sentence.

Why it works: This algorithm ensures that only valid prices are modified, applying the correct discount and formatting. The invariant is that every word is either replaced with its discounted version or remains unchanged, preserving the original sentence structure.

Python Solution

class Solution:
    def discountPrices(self, sentence: str, discount: int) -> str:
        words = sentence.split(' ')
        result = []
        for word in words:
            if word.startswith('$') and len(word) > 1 and word[1:].isdigit():
                price = float(word[1:])
                discounted_price = price * (100 - discount) / 100
                result.append(f"${discounted_price:.2f}")
            else:
                result.append(word)
        return ' '.join(result)

In this Python implementation, we first split the sentence into words, iterate through them, and check if each word is a valid price by verifying it starts with $ and the rest are digits. If it is a valid price, we convert it to a float, apply the discount, format it to two decimal places, and append it to the result list. Non-price words are appended unchanged. Finally, we join all words into a single string to return.

Go Solution

import (
    "fmt"
    "strings"
    "unicode"
)

func discountPrices(sentence string, discount int) string {
    words := strings.Split(sentence, " ")
    for i, word := range words {
        if len(word) > 1 && word[0] == '$' {
            isDigit := true
            for _, ch := range word[1:] {
                if !unicode.IsDigit(ch) {
                    isDigit = false
                    break
                }
            }
            if isDigit {
                var price float64
                fmt.Sscanf(word[1:], "%f", &price)
                discounted := price * float64(100-discount) / 100
                words[i] = fmt.Sprintf("$%.2f", discounted)
            }
        }
    }
    return strings.Join(words, " ")
}

In Go, we similarly split the sentence into words and check each for the $ prefix. We iterate over the characters to ensure they are digits. If valid, we parse the numeric portion using fmt.Sscanf, apply the discount, and format the result with two decimals using fmt.Sprintf. The reconstructed sentence is returned after joining the words.

Worked Examples

Example 1:

Sentence: "there are $1 $2 and 5$ candies in the shop", discount 50.

Split: ["there", "are", "$1", "$2", "and", "5$", "candies", "in", "the", "shop"]
Process each word:

"there" → unchanged
"are" → unchanged
"$1" → valid price → 1 * (100-50)/100 = 0.5 → "$0.50"
"$2" → valid price → 2 * 0.5 = 1.0 → "$1.00"
"and" → unchanged
"5$" → invalid → unchanged
"candies" → unchanged
"in" → unchanged
"the" → unchanged
"shop" → unchanged

Join: "there are $0.50 $1.00 and 5$ candies in the shop"

Example 2:

Sentence: "1 2 $3 4 $5 $6 7 8$ $9 $10$", discount 100.

Split: ["1","2","$3","4","$5","$6","7","8$","$9","$10$"]
Process prices with 100% discount → "$3" → $0.00, "$5" → $0.00, "$6" → $0.00, "$9" → $0.00. Words like "8$" and "$10$" remain unchanged.
Join: "1 2 $0.00 4 $0.00 $0.00 7 8$ $0.00 $10$"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We traverse each word in the sentence once, and each character of each word at most once to check validity.
Space	O(n)	We store the result words in a list of size proportional to the number of words.

The algorithm scales linearly with the length of the sentence. Space is also linear because we need to store the modified sentence.

Test Cases

# provided examples
assert Solution().discountPrices("there are $1 $2 and 5$ candies in the shop", 50) == "there are $0.50 $1.00 and 5$ candies in the shop"
assert Solution().discountPrices("1 2 $3 4 $5 $6 7 8$ $9 $10$", 100) == "1 2 $0.00 4 $0.00 $0.00 7 8$ $0.00 $10$"

# boundary cases
assert Solution().discountPrices("$1234567890", 10) == "$1111111101.00"  # 10-digit number
assert Solution().discountPrices("$0", 50) == "$0.00"  # smallest positive price
assert Solution().discountPrices("no prices here", 50) == "no prices here"  # no price words

# edge numeric cases
assert Solution().discountPrices("$1 $10 $100", 33) == "$0.67 $6.70 $67.00"  # rounding
assert Solution().discountPrices("$5$ $5a $a5 $5", 20) == "$5$ $5a $a5 $4.00"  # mixed invalid prices

Test	Why
"there are $1 $2 ..."	verifies typical discount application and proper formatting
"$1234567890"	tests handling of very large price numbers
"$0"	ensures zero price handled correctly
"no prices here"	sentence with no prices should remain unchanged
"$1 $10 $100"	checks rounding and decimal precision
"$5$ $5a $a5 $5"	verifies handling of invalid price patterns