# Apply Discount to Prices
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/apply-discount-to-prices)
Canonical: https://scaleengineer.com/dsa/problems/apply-discount-to-prices
**Data structures:** String
---
## Problem
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 <= 105`
* `sentence` consists of lowercase English letters, digits, `' '`, and `'$'`.
* `sentence` does not have leading or trailing spaces.
* All words in `sentence` are separated by a single space.
* All prices will be **positive** numbers without leading zeros.
* All prices will have **at most** `10` digits.
* `0 <= discount <= 100`

# Approaches
## Approach 1: Split, Process, and Join
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Split the input `sentence` string into an array of words using the space character as a delimiter.
- Create a `StringBuilder` to 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 `StringBuilder` and return the final string.

## Approach 2: Single-Pass Manual Parsing
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.
**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.
**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 `split` method.
**Cons:** The code involves manual index management, which can be slightly more complex and error-prone than iterating over a pre-split array.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Initialize an empty `StringBuilder` to store the result.
- Use a pointer `i` to 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`.
- 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 `i` to `j + 1` to move to the start of the next word.
- Continue until the entire sentence is processed and return the `StringBuilder`'s content.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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)

```