In this guide, you will get 3556. Sum of Largest Prime Substrings LeetCode Solution with the best time and space complexity. The solution to Sum of Largest Prime Substrings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Sum of Largest Prime Substrings
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.
3556. Sum of Largest Prime Substrings LeetCode Solution in C++
class Solution {
public:
long long sumOfLargestPrimes(string s) {
const int n = s.length();
unordered_set<long> primes;
for (int i = 0; i < n; ++i)
for (int j = i + 1; j <= n; ++j) {
const long num = stol(s.substr(i, j - i));
if (!primes.contains(num) && isPrime(num))
primes.insert(num);
}
vector<long> sortedPrimes{primes.begin(), primes.end()};
ranges::sort(sortedPrimes, greater<>());
return accumulate(
sortedPrimes.begin(),
sortedPrimes.begin() + min(3, static_cast<int>(sortedPrimes.size())),
L);
}
private:
bool isPrime(long num) {
if (num <= 1)
return false;
for (int i = 2; i <= sqrt(num); ++i)
if (num % i == 0)
return false;
return true;
}
}; /* code provided by PROGIEZ */
3556. Sum of Largest Prime Substrings LeetCode Solution in Java
class Solution {
public long sumOfLargestPrimes(String s) {
final int n = s.length();
Set<Long> primes = new HashSet<>();
for (int i = 0; i < n; ++i)
for (int j = i + 1; j <= n; ++j) {
final long num = Long.parseLong(s.substring(i, j));
if (!primes.contains(num) && isPrime(num))
primes.add(num);
}
List<Long> sortedPrimes = new ArrayList<>(primes);
Collections.sort(sortedPrimes, Collections.reverseOrder());
return sortedPrimes.stream().limit(3).mapToLong(Long::longValue).sum();
}
private boolean isPrime(long num) {
if (num <= 1)
return false;
for (int i = 2; i <= Math.sqrt(num); i++)
if (num % i == 0)
return false;
return true;
}
} // code provided by PROGIEZ
3556. Sum of Largest Prime Substrings LeetCode Solution in Python
class Solution:
def sumOfLargestPrimes(self, s: str) -> int:
primes = set()
n = len(s)
for i in range(n):
for j in range(i + 1, n + 1):
num = int(s[i:j])
if num not in primes and self._isPrime(num):
primes.add(num)
top3 = sorted(primes, reverse=True)[:3]
return sum(top3)
def _isPrime(self, n: int) -> bool:
return n > 1 and all(n % i != 0 for i in range(2, math.isqrt(n) + 1)) # code by PROGIEZ
