Sum of Largest Prime Substrings
MedPrompt
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 <= 10sconsists of only digits.
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize an empty
ArrayList<Long>calledprimesto store the unique prime numbers. - Iterate through the string
swith two nested loops to generate all substrings. - For each substring, convert it to a
longnumber. - Check if this number is prime using a helper function
isPrime(long n)that iterates from 2 up ton / 2. - If the number is prime and is not already in the
primeslist (!primes.contains(num)), add it to the list. - After checking all substrings, sort the
primeslist in descending order. - Calculate the sum of the top
kprimes from the sorted list, wherek = Math.min(3, primes.size()). - Return the sum.
Walkthrough
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:
- Initialize an empty
ArrayList<Long>calledprimesto store the unique prime numbers. - Iterate through the string
swith two nested loops to generate all substrings. The outer loop variableiruns from0tos.length() - 1, and the inner loop variablejruns fromitos.length() - 1. - For each pair of
(i, j), extract the substrings.substring(i, j + 1). - Convert the substring to a
longnumber. - Check if this number is prime using a helper function
isPrime(long n). This function will iterate from 2 up ton / 2, and if it finds any divisor, it returnsfalse. - If the number is prime and is not already in the
primeslist (!primes.contains(num)), add it to the list. - After checking all substrings, sort the
primeslist in descending order. - Determine how many primes to sum:
k = Math.min(3, primes.size()). - Calculate the sum of the top
kprimes from the sorted list. - Return the sum.
- Initialize an empty
-
Code Snippet:
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; }}Complexity
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.
Trade-offs
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, withO(P)time for each check wherePis the number of primes found so far.Not feasible for the given constraints where numbers can be large.
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.
Algorithm
- Initialize an empty
HashSet<Long>calledprimeSetto store unique prime numbers. - Use two nested loops to generate all substrings of
s. - For each substring, parse it into a
longnumber. - Check if the number is prime using an efficient
isPrime(long n)helper function that iterates from 2 up tosqrt(n). - If the number is prime, add it to the
primeSet. - After iterating through all substrings, convert the
primeSetinto anArrayList. - Sort the list in descending order.
- Sum the first
kelements, wherekis the minimum of 3 and the list's size. - Return the total sum.
Walkthrough
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:
- Initialize an empty
HashSet<Long>calledprimeSetto store unique prime numbers. - Use two nested loops (
ifrom0ton-1,jfromiton-1) to generate all substrings ofs. - For each substring, parse it into a
longnumber. - 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 tosqrt(n). If any number in this range dividesn,nis not prime. - If the number is prime, add it to the
primeSet. The set automatically ensures that only unique primes are stored. - After iterating through all substrings, convert the
primeSetinto anArrayList. - Sort the list in descending order.
- Sum the first
kelements, wherekis the minimum of 3 and the list's size. - Return the total sum.
- Initialize an empty
-
Code Snippet:
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; }}Complexity
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.
Trade-offs
Pros
Efficient and practical for the given constraints.
The use of
sqrt(n)for primality and aHashSetfor 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").
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.
Algorithm
- Initialize a
HashSet<Long>(primeSet) and aHashMap<Long, Boolean>(memo). - Generate all substrings using nested loops.
- For each substring, parse it to a
longnumber,num. - Check if
numis prime using a memoizedisPrimefunction.- This function first checks if
memocontainsnum. If so, it returns the cached value. - Otherwise, it computes primality (up to
sqrt(n)), stores the result inmemo, and then returns it.
- This function first checks if
- If the number is prime, add it to
primeSet. - After checking all substrings, convert
primeSetto a list, sort it, and sum the top elements.
Walkthrough
This is the most performant approach, as it eliminates redundant primality calculations, which can occur if different substrings evaluate to the same number.
-
Algorithm:
- Initialize a
HashSet<Long>(primeSet) to store unique primes. - Initialize a
HashMap<Long, Boolean>(memo) to cache the results of primality tests. - Generate all substrings using nested loops.
- For each substring, parse it to a
longnumber,num. - Check if
numis prime using a memoizedisPrimefunction.- This function first checks if
memocontainsnum. 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
memofor future use (memo.put(num, result)). - Finally, it returns the computed result.
- This function first checks if
- If the number is prime, add it to
primeSet. - After checking all substrings, convert
primeSetto a list, sort it in descending order, and sum the top three (or fewer) elements.
- Initialize a
-
Code Snippet:
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; }}Complexity
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`.
Trade-offs
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.
Solutions
Solution
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; }}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; }};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:])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.