Problem Description

Given a string s, you need to find all possible substrings that can form prime numbers and calculate the sum of the 3 largest unique prime numbers.

A substring is any contiguous sequence of characters within the string. For example, if s = "123", the substrings are: "1", "2", "3", "12", "23", "123".

When converting a substring to a number:

• Leading zeros are ignored (e.g., "012" becomes 12)
• Each unique prime number is counted only once, even if it appears multiple times through different substrings

The task requires you to:

1. Extract all possible substrings from the given string
2. Convert each substring to an integer and check if it's a prime number
3. Collect all unique prime numbers found
4. Return the sum of the 3 largest unique primes

Special cases:

• If there are fewer than 3 unique prime numbers, return the sum of all available primes
• If no prime numbers can be formed from any substring, return 0

For example, if the string contains substrings that form the primes [2, 3, 5, 7, 11], the answer would be 5 + 7 + 11 = 23 (sum of the 3 largest).

Intuition

The key insight is that we need to explore all possible ways to extract numbers from the string, which naturally leads us to think about substrings. Since we want to find prime numbers, we need to check every possible substring that could represent a valid number.

The brute force approach makes sense here because:

1. We must examine all substrings anyway - there's no way to know which substrings form primes without checking them
2. A substring starting at position i and ending at position j represents a potential number

To build each number from a substring, we can use the digit-by-digit construction method: starting from position i, we keep extending to the right, building the number by multiplying the current value by 10 and adding the new digit. For example, to build 123 from string "123": first we have 1, then 1 * 10 + 2 = 12, then 12 * 10 + 3 = 123.

Since we only care about unique primes (each prime counted once), a set data structure is perfect for storing the primes we find - it automatically handles duplicates for us.

The primality check is straightforward: for each number x, we check if any number from 2 to sqrt(x) divides it evenly. If none do, it's prime. We only need to check up to sqrt(x) because if x has a divisor greater than sqrt(x), it must also have a corresponding divisor less than sqrt(x).

Finally, to get the 3 largest primes, we can sort the set and take the last 3 elements. Python's slice notation [-3:] elegantly handles the case where we have fewer than 3 primes - it just returns whatever elements are available.

Learn more about Math and Sorting patterns.

Solution Approach

The solution uses an enumeration approach combined with a hash table (set) to find all unique prime numbers from the string's substrings.

Step 1: Initialize Data Structures

• Create an empty set st to store unique prime numbers
• Get the length n of the input string

Step 2: Enumerate All Substrings

• Use two nested loops to generate all possible substrings:
  • Outer loop: i from 0 to n-1 (starting position)
  • Inner loop: j from i to n-1 (ending position)
• For each starting position i, initialize x = 0 to build the number

Step 3: Build Numbers from Substrings

• For each character at position j, convert it to a digit and append to the current number:
  • x = x * 10 + int(s[j])
• This builds the number digit by digit. For example, with substring "123":
  • First iteration: x = 0 * 10 + 1 = 1
  • Second iteration: x = 1 * 10 + 2 = 12
  • Third iteration: x = 12 * 10 + 3 = 123

Step 4: Check for Primality

• Implement the is_prime function:
  • Numbers less than 2 are not prime
  • For numbers ≥ 2, check if any number from 2 to sqrt(x) divides x
  • Use all(x % i for i in range(2, int(sqrt(x)) + 1)) to verify no divisors exist
• If x is prime, add it to the set st

Step 5: Calculate the Result

• Sort the set of primes in ascending order: sorted(st)
• Take the last 3 elements using slice notation: [-3:]
• Return the sum of these elements

The beauty of this approach is that:

• The set automatically handles duplicate primes
• Python's slice notation [-3:] gracefully handles cases with fewer than 3 primes
• The sum of an empty list returns 0, handling the case with no primes

Time Complexity: O(n² × √m) where n is the string length and m is the maximum number value Space Complexity: O(k) where k is the number of unique primes found

Example Walkthrough

Let's walk through the solution with the string s = "2357".

Step 1: Initialize

• Create empty set st = {}
• String length n = 4

Step 2-4: Generate substrings and check for primes

Starting from position i = 0 (character '2'):

• j = 0: substring "2", x = 0 * 10 + 2 = 2
  • Is 2 prime? Yes → Add to set: st = {2}
• j = 1: substring "23", x = 2 * 10 + 3 = 23
  • Is 23 prime? Check divisors from 2 to 4 (√23 ≈ 4.8)
  • 23 % 2 = 1, 23 % 3 = 2, 23 % 4 = 3 → Yes, prime → st = {2, 23}
• j = 2: substring "235", x = 23 * 10 + 5 = 235
  • Is 235 prime? 235 % 5 = 0 → No, not prime
• j = 3: substring "2357", x = 235 * 10 + 7 = 2357
  • Is 2357 prime? Check up to √2357 ≈ 48
  • 2357 is actually prime → st = {2, 23, 2357}

Starting from position i = 1 (character '3'):

• j = 1: substring "3", x = 0 * 10 + 3 = 3
  • Is 3 prime? Yes → st = {2, 3, 23, 2357}
• j = 2: substring "35", x = 3 * 10 + 5 = 35
  • Is 35 prime? 35 % 5 = 0 → No
• j = 3: substring "357", x = 35 * 10 + 7 = 357
  • Is 357 prime? 357 % 3 = 0 → No

Starting from position i = 2 (character '5'):

• j = 2: substring "5", x = 0 * 10 + 5 = 5
  • Is 5 prime? Yes → st = {2, 3, 5, 23, 2357}
• j = 3: substring "57", x = 5 * 10 + 7 = 57
  • Is 57 prime? 57 % 3 = 0 → No

Starting from position i = 3 (character '7'):

• j = 3: substring "7", x = 0 * 10 + 7 = 7
  • Is 7 prime? Yes → st = {2, 3, 5, 7, 23, 2357}

Step 5: Find sum of 3 largest primes

• Final set of primes: {2, 3, 5, 7, 23, 2357}
• Sort the set: [2, 3, 5, 7, 23, 2357]
• Take last 3 elements: [7, 23, 2357]
• Return sum: 7 + 23 + 2357 = 2387

The solution efficiently handles all edge cases:

• If we had found only 2 primes like {3, 7}, the slice [-3:] would return [3, 7] and sum to 10
• If no primes were found, the empty list would sum to 0

Solution Implementation

Time and Space Complexity

Time Complexity: O(n² × √M)

The algorithm uses nested loops to generate all possible substrings:

• The outer loop runs n times (where n is the length of the string)
• The inner loop runs up to n times for each iteration of the outer loop
• This gives us O(n²) substring generations

For each substring generated, we check if it's prime using the is_prime function:

• The is_prime function iterates from 2 to √x where x is the numeric value of the substring
• The maximum value of a substring is M (the largest possible numeric value from the string)
• Therefore, the prime check takes O(√M) time

Combining these operations: O(n²) substrings × O(√M) prime check = O(n² × √M)

Additional operations like adding to set (O(1)), sorting (O(k log k) where k ≤ n²), and summing (O(1)) don't dominate the complexity.

Space Complexity: O(n²)

The space is primarily consumed by:

• The set st which stores all prime numbers found from substrings
• In the worst case, all O(n²) possible substrings could be prime numbers
• Each number in the set takes O(1) space
• Therefore, the total space complexity is O(n²)

The temporary variables and the sorted list creation don't exceed this bound.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow with Large Numbers

Pitfall: When processing long strings, the accumulated number current_num can become extremely large, potentially exceeding typical integer limits in some languages or causing performance issues during primality checking.

For example, a string like "9876543210123456789" would generate massive numbers that are computationally expensive to check for primality.

Solution:

• Add an upper bound check to skip numbers above a reasonable threshold
• Consider limiting the maximum substring length to prevent overflow

MAX_PRIME_CHECK = 10**9  # Set reasonable upper bound

for start_idx in range(n):
    current_num = 0
    for end_idx in range(start_idx, n):
        current_num = current_num * 10 + int(s[end_idx])
      
        # Skip if number exceeds reasonable bounds
        if current_num > MAX_PRIME_CHECK:
            break
          
        if is_prime(current_num):
            prime_set.add(current_num)

2. Inefficient Primality Testing for Large Numbers

Pitfall: The basic primality test iterates through all numbers from 2 to √n, which becomes slow for large numbers. If the string generates many large numbers, the overall performance degrades significantly.

Solution:

• Implement optimized primality testing that checks for 2 and odd numbers only
• Use memoization to cache previously computed prime checks

# Optimized primality check
def is_prime(num: int) -> bool:
    if num < 2:
        return False
    if num == 2:
        return True
    if num % 2 == 0:
        return False
  
    # Only check odd divisors
    for i in range(3, int(sqrt(num)) + 1, 2):
        if num % i == 0:
            return False
    return True

# Or use memoization
prime_cache = {}

def is_prime_cached(num: int) -> bool:
    if num in prime_cache:
        return prime_cache[num]
  
    result = is_prime(num)
    prime_cache[num] = result
    return result

3. Handling Leading Zeros Incorrectly

Pitfall: The current implementation treats "01", "001", etc. as distinct from "1" during substring generation, but they all represent the same number. This isn't necessarily wrong since the set handles duplicates, but it causes unnecessary primality checks.

Solution:

• Skip substrings that start with '0' (except for the single digit '0' itself)

for start_idx in range(n):
    # Skip if starting with '0' and not a single '0'
    if s[start_idx] == '0':
        # Only check single '0', skip multi-digit numbers starting with 0
        if is_prime(0):  # Will return False
            prime_set.add(0)
        continue
  
    current_num = 0
    for end_idx in range(start_idx, n):
        current_num = current_num * 10 + int(s[end_idx])
        if is_prime(current_num):
            prime_set.add(current_num)

4. Memory Issues with Large Prime Sets

Pitfall: For strings with many digits, the set of unique primes could grow very large, consuming significant memory.

Solution:

• Maintain only the top 3 primes using a min-heap instead of storing all primes

import heapq

def sumOfLargestPrimes(self, s: str) -> int:
    min_heap = []  # Store only top 3 primes
    seen_primes = set()  # Track which primes we've seen
  
    for start_idx in range(n):
        current_num = 0
        for end_idx in range(start_idx, n):
            current_num = current_num * 10 + int(s[end_idx])
          
            if current_num not in seen_primes and is_prime(current_num):
                seen_primes.add(current_num)
              
                if len(min_heap) < 3:
                    heapq.heappush(min_heap, current_num)
                elif current_num > min_heap[0]:
                    heapq.heapreplace(min_heap, current_num)
  
    return sum(min_heap)