# Sum of Largest Prime Substrings
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/sum-of-largest-prime-substrings)
Canonical: https://scaleengineer.com/dsa/problems/sum-of-largest-prime-substrings
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Hash Table, String
---
## Problem
Given a string `s`, find the sum of the **3 largest unique prime numbers** that can be formed using any of its **substrings**.

Return the **sum** of the three largest unique prime numbers that can be formed. If fewer than three exist, return the sum of **all** available primes. If no prime numbers can be formed, return 0.

**Note:** Each prime number should be counted only **once**, even if it appears in **multiple** substrings. Additionally, when converting a substring to an integer, any leading zeros are ignored.

**Example 1:**

**Input:** s = "12234"

**Output:** 1469

**Explanation:**

* The unique prime numbers formed from the substrings of `"12234"` are 2, 3, 23, 223, and 1223.
* The 3 largest primes are 1223, 223, and 23\. Their sum is 1469.

**Example 2:**

**Input:** s = "111"

**Output:** 11

**Explanation:**

* The unique prime number formed from the substrings of `"111"` is 11.
* Since there is only one prime number, the sum is 11.

**Constraints:**

* `1 <= s.length <= 10`
* `s` consists of only digits.

# Approaches
## Naive Brute-Force
This approach systematically generates every possible substring from the input string `s`. For each substring, it converts it into a number and then checks if that number is prime. The primality test is done in a simple but inefficient way: by checking for divisibility by every number from 2 up to half of the number itself. To ensure uniqueness, the found prime numbers are stored in a list, and before adding a new prime, the entire list is scanned to see if it's already present. Finally, the list of unique primes is sorted to find the largest ones, and their sum is calculated.
**Time:** O(N^2 * (L + V + P)) where N is the length of the string, L is substring length, V is the numeric value of the substring, and P is the number of primes found. The `isPrime` check takes up to O(V) time. The `primes.contains()` check takes O(P) time. This is extremely slow. · **Space:** O(N^2) to store the list of unique primes. In the worst case, all `N*(N+1)/2` substrings could be prime.
**Pros:** Conceptually very simple and easy to write.
**Cons:** Extremely inefficient due to the primality test running up to `n/2`.; Using a list and `contains()` for checking duplicates is slow, with `O(P)` time for each check where `P` is the number of primes found so far.; Not feasible for the given constraints where numbers can be large.
### Explanation
This method involves a brute-force iteration over all substrings. For each valid number formed, it performs a primality test. The main drawbacks are the inefficient primality check and the method of handling duplicates.

- **Algorithm**:
  1. Initialize an empty `ArrayList<Long>` called `primes` to store the unique prime numbers.
  2. Iterate through the string `s` with two nested loops to generate all substrings. The outer loop variable `i` runs from `0` to `s.length() - 1`, and the inner loop variable `j` runs from `i` to `s.length() - 1`.
  3. For each pair of `(i, j)`, extract the substring `s.substring(i, j + 1)`.
  4. Convert the substring to a `long` number.
  5. Check if this number is prime using a helper function `isPrime(long n)`. This function will iterate from 2 up to `n / 2`, and if it finds any divisor, it returns `false`.
  6. If the number is prime and is not already in the `primes` list (`!primes.contains(num)`), add it to the list.
  7. After checking all substrings, sort the `primes` list in descending order.
  8. Determine how many primes to sum: `k = Math.min(3, primes.size())`.
  9. Calculate the sum of the top `k` primes from the sorted list.
  10. Return the sum.

- **Code Snippet**:
```java
import java.util.*;

class Solution {
    // Inefficient primality test
    private boolean isPrime(long n) {
        if (n <= 1) {
            return false;
        }
        for (long i = 2; i <= n / 2; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public long sumOfLargestPrimeSubstrings(String s) {
        List<Long> primes = new ArrayList<>();
        int n = s.length();

        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                String sub = s.substring(i, j + 1);
                try {
                    long num = Long.parseLong(sub);
                    if (isPrime(num)) {
                        if (!primes.contains(num)) {
                            primes.add(num);
                        }
                    }
                } catch (NumberFormatException e) {
                    // Ignore invalid numbers
                }
            }
        }

        Collections.sort(primes, Collections.reverseOrder());

        long sum = 0;
        int count = Math.min(3, primes.size());
        for (int i = 0; i < count; i++) {
            sum += primes.get(i);
        }

        return sum;
    }
}
```
### Algorithm
- Initialize an empty `ArrayList<Long>` called `primes` to store the unique prime numbers.
- Iterate through the string `s` with two nested loops to generate all substrings.
- For each substring, convert it to a `long` number.
- Check if this number is prime using a helper function `isPrime(long n)` that iterates from 2 up to `n / 2`.
- If the number is prime and is not already in the `primes` list (`!primes.contains(num)`), add it to the list.
- After checking all substrings, sort the `primes` list in descending order.
- Calculate the sum of the top `k` primes from the sorted list, where `k = Math.min(3, primes.size())`.
- Return the sum.

## Optimized Brute-Force with Efficient Primality Test
This approach is a significant improvement over the naive one. It still generates all substrings and checks them for primality, but it employs two key optimizations. First, it uses a much faster primality test algorithm: trial division up to the square root of the number. Second, it uses a `HashSet` to store the unique prime numbers. A `HashSet` provides average `O(1)` time for adding elements and automatically handles duplicates, which is much more efficient than using a list and manually checking for existence.
**Time:** O(N^2 * (L + sqrt(V))), where N is string length, L is substring length, and V is the numeric value. The `isPrime` check takes O(sqrt(V)) time, and `HashSet` operations are O(1) on average. This is efficient enough for the problem's constraints. · **Space:** O(N^2) to store the `HashSet` of unique primes.
**Pros:** Efficient and practical for the given constraints.; The use of `sqrt(n)` for primality and a `HashSet` for uniqueness are standard best practices.
**Cons:** Repeatedly calculates primality for the same number if it's formed from different substrings (e.g., "7" and "07").
### Explanation
This approach refines the brute-force method by incorporating standard optimizations for primality testing and handling unique elements, making it highly effective for the given constraints.

- **Algorithm**:
  1. Initialize an empty `HashSet<Long>` called `primeSet` to store unique prime numbers.
  2. Use two nested loops (`i` from `0` to `n-1`, `j` from `i` to `n-1`) to generate all substrings of `s`.
  3. For each substring, parse it into a `long` number.
  4. Check if the number is prime using an efficient `isPrime(long n)` helper function. This function first handles base cases (numbers <= 1). Then, it iterates from 2 up to `sqrt(n)`. If any number in this range divides `n`, `n` is not prime.
  5. If the number is prime, add it to the `primeSet`. The set automatically ensures that only unique primes are stored.
  6. After iterating through all substrings, convert the `primeSet` into an `ArrayList`.
  7. Sort the list in descending order.
  8. Sum the first `k` elements, where `k` is the minimum of 3 and the list's size.
  9. Return the total sum.

- **Code Snippet**:
```java
import java.util.*;

class Solution {
    // Efficient primality test
    private boolean isPrime(long n) {
        if (n <= 1) return false;
        if (n <= 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;
        for (long i = 5; i * i <= n; i = i + 6) {
            if (n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }

    public long sumOfLargestPrimeSubstrings(String s) {
        Set<Long> primeSet = new HashSet<>();
        int n = s.length();

        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                String sub = s.substring(i, j + 1);
                try {
                    long num = Long.parseLong(sub);
                    if (isPrime(num)) {
                        primeSet.add(num);
                    }
                } catch (NumberFormatException e) {
                    // Ignore
                }
            }
        }

        List<Long> primes = new ArrayList<>(primeSet);
        Collections.sort(primes, Collections.reverseOrder());

        long sum = 0;
        int count = Math.min(3, primes.size());
        for (int i = 0; i < count; i++) {
            sum += primes.get(i);
        }

        return sum;
    }
}
```
### Algorithm
- Initialize an empty `HashSet<Long>` called `primeSet` to store unique prime numbers.
- Use two nested loops to generate all substrings of `s`.
- For each substring, parse it into a `long` number.
- Check if the number is prime using an efficient `isPrime(long n)` helper function that iterates from 2 up to `sqrt(n)`.
- If the number is prime, add it to the `primeSet`.
- After iterating through all substrings, convert the `primeSet` into an `ArrayList`.
- Sort the list in descending order.
- Sum the first `k` elements, where `k` is the minimum of 3 and the list's size.
- Return the total sum.

## Optimized Brute-Force with Memoization
This approach builds upon the optimized brute-force method by adding a layer of memoization (caching). It recognizes that the same number can be generated from different substrings (e.g., "7", "07", "007"). To avoid re-computing the primality of the same number multiple times, we can store the results of our `isPrime` function in a cache (like a `HashMap`). When `isPrime` is called for a number, it first checks the cache. If the result is there, it's returned instantly; otherwise, the primality is computed, and the result is stored in the cache before being returned.
**Time:** O(N^2 * L + U * sqrt(V)), where N is string length, L is substring length, U is the number of *unique* numeric values from substrings, and V is the maximum numeric value. The primality of each unique number is computed only once. · **Space:** O(N^2) to store the `HashSet` of primes and the `HashMap` for memoization. The number of unique substrings is at most `N*(N+1)/2`.
**Pros:** Most efficient approach as it avoids redundant computations.; It's a robust solution that would scale better if the number of duplicate substrings were higher.
**Cons:** Slightly more complex to implement due to the memoization cache.; For the given small constraints (N <= 10), the performance gain over the non-memoized optimized approach might be negligible.
### Explanation
This is the most performant approach, as it eliminates redundant primality calculations, which can occur if different substrings evaluate to the same number.

- **Algorithm**:
  1. Initialize a `HashSet<Long>` (`primeSet`) to store unique primes.
  2. Initialize a `HashMap<Long, Boolean>` (`memo`) to cache the results of primality tests.
  3. Generate all substrings using nested loops.
  4. For each substring, parse it to a `long` number, `num`.
  5. Check if `num` is prime using a memoized `isPrime` function.
     - This function first checks if `memo` contains `num`. If so, it returns the cached boolean value.
     - If not, it computes the primality using the efficient trial division method (up to `sqrt(n)`).
     - It then stores the result in `memo` for future use (`memo.put(num, result)`).
     - Finally, it returns the computed result.
  6. If the number is prime, add it to `primeSet`.
  7. After checking all substrings, convert `primeSet` to a list, sort it in descending order, and sum the top three (or fewer) elements.

- **Code Snippet**:
```java
import java.util.*;

class Solution {
    private Map<Long, Boolean> memo = new HashMap<>();

    private boolean isPrime(long n) {
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        if (n <= 1) {
            memo.put(n, false);
            return false;
        }
        if (n <= 3) {
            memo.put(n, true);
            return true;
        }
        if (n % 2 == 0 || n % 3 == 0) {
            memo.put(n, false);
            return false;
        }
        for (long i = 5; i * i <= n; i = i + 6) {
            if (n % i == 0 || n % (i + 2) == 0) {
                memo.put(n, false);
                return false;
            }
        }
        memo.put(n, true);
        return true;
    }

    public long sumOfLargestPrimeSubstrings(String s) {
        Set<Long> primeSet = new HashSet<>();
        int n = s.length();

        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                String sub = s.substring(i, j + 1);
                try {
                    long num = Long.parseLong(sub);
                    if (isPrime(num)) {
                        primeSet.add(num);
                    }
                } catch (NumberFormatException e) {
                    // Ignore
                }
            }
        }

        List<Long> primes = new ArrayList<>(primeSet);
        Collections.sort(primes, Collections.reverseOrder());

        long sum = 0;
        int count = Math.min(3, primes.size());
        for (int i = 0; i < count; i++) {
            sum += primes.get(i);
        }

        return sum;
    }
}
```
### Algorithm
- Initialize a `HashSet<Long>` (`primeSet`) and a `HashMap<Long, Boolean>` (`memo`).
- Generate all substrings using nested loops.
- For each substring, parse it to a `long` number, `num`.
- Check if `num` is prime using a memoized `isPrime` function.
  - This function first checks if `memo` contains `num`. If so, it returns the cached value.
  - Otherwise, it computes primality (up to `sqrt(n)`), stores the result in `memo`, and then returns it.
- If the number is prime, add it to `primeSet`.
- After checking all substrings, convert `primeSet` to a list, sort it, and sum the top elements.

# Solutions
### Java

```java
class Solution {
public
  long sumOfLargestPrimes(String s) {
    Set<Long> st = new HashSet<>();
    int n = s.length();
    for (int i = 0; i < n; i++) {
      long x = 0;
      for (int j = i; j < n; j++) {
        x = x * 10 + (s.charAt(j) - '0');
        if (is_prime(x)) {
          st.add(x);
        }
      }
    }
    List<Long> sorted = new ArrayList<>(st);
    Collections.sort(sorted);
    long ans = 0;
    int start = Math.max(0, sorted.size() - 3);
    for (int idx = start; idx < sorted.size(); idx++) {
      ans += sorted.get(idx);
    }
    return ans;
  }
private
  boolean is_prime(long x) {
    if (x < 2)
      return false;
    for (long i = 2; i * i <= x; i++) {
      if (x % i == 0)
        return false;
    }
    return true;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long sumOfLargestPrimes(string s) {
    unordered_set<long long> st;
    int n = s.size();
    for (int i = 0; i < n; ++i) {
      long long x = 0;
      for (int j = i; j < n; ++j) {
        x = x * 10 + (s[j] - '0');
        if (is_prime(x)) {
          st.insert(x);
        }
      }
    }
    vector<long long> sorted(st.begin(), st.end());
    sort(sorted.begin(), sorted.end());
    long long ans = 0;
    int cnt = 0;
    for (int i = (int)sorted.size() - 1; i >= 0 && cnt < 3; --i, ++cnt) {
      ans += sorted[i];
    }
    return ans;
  }

private:
  bool is_prime(long long x) {
    if (x < 2)
      return false;
    for (long long i = 2; i * i <= x; ++i) {
      if (x % i == 0)
        return false;
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    def sumOfLargestPrimes(self, s: str) -> int: def is_prime(x: int) -> bool: if x < 2: return False return all(x % i for i in range(2, int(sqrt(x)) + 1)) st = set() n = len(s) for i in range(n): x = 0 for j in range(i, n): x = x * 10 + int(s[j]) if is_prime(x): st . add(x) return sum(sorted(st)[- 3:])

```