3556. Sum of Largest Prime Substrings

MediumHash TableMathStringNumber TheorySorting

Problem Description

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.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

To find the required sum, consider that any substring of s could represent a number, and some of those numbers might be prime. The task is to check all possible substrings, ignore any leading zeros, and see if the number formed is a prime. Since duplicate numbers can appear from different substrings, only count each distinct prime once.

After identifying all unique primes from all substrings, sort them and add up the top three largest ones. If there are fewer than three, just add whatever primes are available. This method ensures we don’t miss any possibilities and handle duplicates correctly.

Solution Approach

We first need to consider every possible substring in the string s, since any of them could turn into a candidate number. To manage this, use nested loops: the outer loop sets the starting index and the inner loop extends to every possible ending index.

For each substring, convert it to an integer by ignoring any leading zeros (this happens naturally if we build the number digit by digit). Before accepting a number, check if it is a prime. This can be done using the classic prime checking method: for an integer x, check divisibility by all integers from 2 up to sqrt(x).

To make sure we count only unique primes, use a set (for example, st in the code) to collect the prime numbers found so far.

After going through all substrings and collecting all unique primes, sort these primes in ascending order. The result is the sum of the largest three primes (use array slicing, like sorted(st)[-3:], to select them). If there are fewer than three primes, sum up all that are available. If there are no primes, return 0.

Overall, the core steps are:

Enumerate all substrings.
Check each substring (as a number) for primality.
Store found primes in a set (set ensures uniqueness).
Sort and sum the top three largest primes or as many as exist.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let’s walk through an example with the string: s = "3173".

Step 1: Enumerate All Substrings

List all possible contiguous substrings:

"3"
"1"
"7"
"3"
"31"
"17"
"73"
"317"
"173"
"3173"

Step 2: Convert to Integers, Ignore Leading Zeros

For "3173", there are no substrings with leading zeros, so all substrings can be directly converted to integers.

Step 3: Check Primality and Collect Uniques

Now check each converted number:

"3" → 3 (prime)
"1" → 1 (not prime)
"7" → 7 (prime)
"3" (again) → already considered
"31" → 31 (prime)
"17" → 17 (prime)
"73" → 73 (prime)
"317" → 317 (prime)
"173" → 173 (prime)
"3173" → 3173 (not prime)

Collect unique primes into a set: {3, 7, 17, 31, 73, 173, 317}

Step 4: Sort and Sum the Three Largest

Sort: [3, 7, 17, 31, 73, 173, 317] Three largest are: 73, 173, 317

Sum = 73 + 173 + 317 = 563

Result

The sum of the three largest unique primes from substrings of "3173" is 563.

Solution Implementation

1from math import sqrt
2
3class Solution:
4    def sumOfLargestPrimes(self, s: str) -> int:
5        # Helper function to check if a given number is prime
6        def is_prime(x: int) -> bool:
7            if x < 2:
8                return False
9            for i in range(2, int(sqrt(x)) + 1):
10                if x % i == 0:
11                    return False
12            return True
13
14        unique_primes = set()
15        n = len(s)
16
17        # Iterate through all substrings of s and convert them to integers
18        for start in range(n):
19            num = 0
20            for end in range(start, n):
21                num = num * 10 + int(s[end])   # Build the new number
22                if is_prime(num):
23                    unique_primes.add(num)      # Add the prime to the set
24
25        # Get the 3 largest primes and sum them
26        return sum(sorted(unique_primes)[-3:])
27

1class Solution {
2    // Main method to compute the sum of the 3 largest unique prime substrings in s
3    public long sumOfLargestPrimes(String s) {
4        Set<Long> uniquePrimes = new HashSet<>();
5        int length = s.length();
6
7        // Generate all possible numeric substrings
8        for (int startIndex = 0; startIndex < length; startIndex++) {
9            long number = 0;
10            // Extend substring from startIndex to end of string
11            for (int endIndex = startIndex; endIndex < length; endIndex++) {
12                // Form the number incrementally
13                number = number * 10 + (s.charAt(endIndex) - '0');
14                // Check if number is prime and add to set
15                if (is_prime(number)) {
16                    uniquePrimes.add(number);
17                }
18            }
19        }
20
21        // Sort the unique primes in ascending order
22        List<Long> sortedPrimes = new ArrayList<>(uniquePrimes);
23        Collections.sort(sortedPrimes);
24
25        // Sum the 3 largest primes (or less if insufficient primes)
26        long sum = 0;
27        int count = sortedPrimes.size();
28        int fromIndex = Math.max(0, count - 3);
29        for (int i = fromIndex; i < count; i++) {
30            sum += sortedPrimes.get(i);
31        }
32        return sum;
33    }
34
35    // Helper method to check if a number is prime
36    private boolean is_prime(long number) {
37        if (number < 2) return false;
38        for (long divisor = 2; divisor * divisor <= number; divisor++) {
39            if (number % divisor == 0) return false;
40        }
41        return true;
42    }
43}
44

1#include <unordered_set>
2#include <vector>
3#include <algorithm>
4#include <string>
5
6class Solution {
7public:
8    // Calculates the sum of the 3 largest unique prime numbers
9    // extracted from all possible substrings of s.
10    long long sumOfLargestPrimes(std::string s) {
11        std::unordered_set<long long> uniquePrimes;
12        int n = s.size();
13
14        // Extract all possible substrings as numbers and check if they are prime
15        for (int i = 0; i < n; ++i) {
16            long long number = 0;
17            for (int j = i; j < n; ++j) {
18                // Form the number by appending the digit
19                number = number * 10 + (s[j] - '0');
20                if (is_prime(number)) {
21                    uniquePrimes.insert(number);
22                }
23            }
24        }
25
26        // Copy the primes into a vector and sort in ascending order
27        std::vector<long long> sortedPrimes(uniquePrimes.begin(), uniquePrimes.end());
28        std::sort(sortedPrimes.begin(), sortedPrimes.end());
29
30        long long sum = 0;
31        int count = 0;
32        // Add the largest 3 primes to the sum
33        for (int i = static_cast<int>(sortedPrimes.size()) - 1; i >= 0 && count < 3; --i, ++count) {
34            sum += sortedPrimes[i];
35        }
36        return sum;
37    }
38
39private:
40    // Checks if a number is prime
41    bool is_prime(long long x) {
42        if (x < 2) return false;
43        for (long long i = 2; i * i <= x; ++i) {
44            if (x % i == 0) return false;
45        }
46        return true;
47    }
48};
49

1/**
2 * Returns the sum of the three largest unique prime numbers
3 * that can be formed by any contiguous substring of the input string.
4 * @param s The input string consisting of digits
5 * @returns The sum of the three largest unique prime numbers
6 */
7function sumOfLargestPrimes(s: string): number {
8    // Set to store unique prime numbers found from all substrings
9    const primesSet = new Set<number>();
10    const strLen = s.length;
11
12    // Iterate over all possible starting indices of substrings
13    for (let start = 0; start < strLen; start++) {
14        let currentNum = 0;
15        // Build substring numbers one digit at a time
16        for (let end = start; end < strLen; end++) {
17            currentNum = currentNum * 10 + Number(s[end]);
18            // If this number is prime, add to set
19            if (isPrime(currentNum)) {
20                primesSet.add(currentNum);
21            }
22        }
23    }
24
25    // Convert set to array and sort in ascending order
26    const sortedPrimes = Array.from(primesSet).sort((a, b) => a - b);
27    // Get the last three (the largest three primes)
28    const largestThree = sortedPrimes.slice(-3);
29    // Sum and return
30    return largestThree.reduce((sum, value) => sum + value, 0);
31}
32
33/**
34 * Checks if a given number is a prime.
35 * @param num The number to check for primality
36 * @returns True if the number is prime, false otherwise
37 */
38function isPrime(num: number): boolean {
39    if (num < 2) return false;
40    for (let factor = 2; factor * factor <= num; factor++) {
41        if (num % factor === 0) return false;
42    }
43    return true;
44}
45

Time and Space Complexity

The time complexity of the code is O(n^2 * sqrt(M)), where n is the length of the input string s, and M is the maximum numerical value formed by any substring of s. This is because for each substring (there are O(n^2) such substrings), the code checks primality, which takes O(sqrt(M)) time for a number up to M.

The space complexity is O(n^2), as the set st may store up to O(n^2) distinct substrings (in the worst case where all substrings are both prime and unique).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: