#3556

Medium

LeetCode Problem Workspace

Sum of Largest Prime Substrings

Compute the sum of the three largest unique primes from all substrings using hash table plus math efficiently.

hash table math string sorting number theory

Problem Statement

Given a string of digits, identify all distinct prime numbers formed by any of its contiguous substrings. Leading zeros are ignored, and each prime is counted only once regardless of duplicates in different substrings.

Return the sum of the three largest unique prime numbers discovered. If fewer than three unique primes exist, sum all available primes. If no prime numbers can be formed, return 0. Ensure efficient handling for strings up to length 10 using hash table and math-based primality checks.

Examples

Example 1

Input: s = "12234"

Output: 1469

Example 2

Input: s = "111"

Output: 11

Constraints

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

Solution Approach

Generate Substrings and Convert

Iterate through all possible substrings of the input string. Convert each substring to an integer while ignoring leading zeros, and collect potential candidate numbers for primality testing.

Check Primality Efficiently

Use a math-based primality test for each candidate number. Store confirmed primes in a hash table to maintain uniqueness and avoid counting duplicates from multiple substrings.

Sum the Largest Primes

Sort the unique primes stored in the hash table in descending order and sum the top three. If fewer than three primes exist, sum all available ones. Return 0 if no primes are found.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is roughly O(n^3) due to generating all substrings and checking each for primality. Space complexity is O(k) where k is the number of unique prime numbers stored in the hash table.

What Interviewers Usually Probe

Focus on hash table usage to prevent duplicate prime counting from overlapping substrings.
Expect efficient math checks for primality due to potential large numeric substrings.
Clarify handling of leading zeros and small input strings.

Common Pitfalls or Variants

Common pitfalls

Forgetting to ignore leading zeros when converting substrings to integers.
Counting the same prime multiple times if it appears in different substrings.
Inefficient primality checks causing timeouts on larger numeric substrings.

Follow-up variants

Return the sum of the k largest unique prime substrings instead of three.
Count primes formed only by substrings of a fixed length.
Compute the product instead of the sum of the largest prime substrings.

FAQ

What exactly is a prime substring in this problem?

A prime substring is any contiguous sequence of digits from the input string that converts to a prime number, ignoring leading zeros.

How should I handle repeated primes from different substrings?

Store primes in a hash table to count each prime only once, even if it appears in multiple substrings.

Can I use GhostInterview to quickly generate candidate numbers?

Yes, GhostInterview iterates over all substrings efficiently and tracks unique candidates for primality checking.

What if there are fewer than three primes?

Return the sum of all available unique primes. If none exist, return 0.

Does the Hash Table plus Math pattern apply here?

Absolutely, hash tables handle uniqueness while math functions efficiently test for primality across substrings.

terminal

Solution

Solution 1: Enumeration + Hash Table

We can enumerate all substrings and check whether they are prime numbers. Since the problem requires us to return the sum of the largest 3 distinct primes, we can use a hash table to store all the primes.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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:])

Continue Practicing

#2949 count beautiful substrings ii #2947 count beautiful substrings i #3545 minimum deletions for at most k distinct characters