LeetCode 3556 - Sum of Largest Prime Substrings

The problem requires identifying prime numbers from all possible substrings of a given string of digits and summing the three largest unique primes.

leetcodemediumhash-tablemathstringsortingnumber-theory

LeetCode Problem 3556

Difficulty: 🟡 Medium
Topics: Hash Table, Math, String, Sorting, Number Theory

Solution

Problem Understanding

The problem requires identifying prime numbers from all possible substrings of a given string of digits and summing the three largest unique primes. In simpler terms, given a string s of length up to 10, we must consider every contiguous sequence of digits, convert it to an integer (ignoring any leading zeros), and check whether it is a prime number. Only distinct primes are counted, and we sum the three largest among them. If fewer than three unique primes exist, we sum all that are present. If no primes exist, we return 0.

The constraints indicate that the input string is short (1 <= s.length <= 10), so generating all substrings is computationally feasible because the total number of substrings of length n is n*(n+1)/2, which is at most 55 when n=10. Another important consideration is handling leading zeros correctly and ensuring that repeated substrings or repeated prime numbers are only counted once. Edge cases include strings containing only zeros, strings with a single digit, and strings with repeated digits.

Approaches

The brute-force approach involves generating all possible substrings, converting them to integers, checking primality for each, collecting all primes in a set, sorting them in descending order, and summing the top three. This approach works because of the small input size but can be made more efficient with careful primality checking.

The key insight for optimization is to use a hash set to ensure uniqueness and to implement an efficient prime check. For small numbers (up to 10^10 in theory, but actually bounded by 1000000000 since the string length is at most 10), trial division up to the square root is sufficient. Sorting is straightforward given the small number of unique primes.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3 * sqrt(m)) O(n^2) Generate all substrings (O(n^2)), convert to int, check prime with trial division (O(sqrt(m)))
Optimal O(n^3 * sqrt(m)) O(n^2) Same as brute force but uses a set to store unique primes and early slicing optimizations; negligible difference given constraints

Algorithm Walkthrough

  1. Initialize an empty set unique_primes to store all prime numbers found from substrings.
  2. Iterate over every possible starting index i of a substring.
  3. For each starting index, iterate over every possible ending index j to form substrings s[i:j+1].
  4. Convert each substring to an integer using standard integer parsing, which automatically removes leading zeros.
  5. Check whether the integer is prime using trial division up to its square root.
  6. If the number is prime, add it to the set unique_primes to maintain uniqueness.
  7. After all substrings are processed, convert the set into a list and sort it in descending order.
  8. Take the top three elements of this sorted list (or all elements if fewer than three exist) and compute their sum.
  9. Return the computed sum. If no primes exist, the set is empty and the sum is 0.

Why it works: The algorithm systematically examines every substring and only adds a number to the set if it is prime. The set ensures uniqueness, while the sorting step ensures that the three largest numbers are chosen. The algorithm respects all problem constraints, including handling leading zeros and repeated primes.

Python Solution

from math import isqrt
from typing import List

class Solution:
    def sumOfLargestPrimes(self, s: str) -> int:
        def is_prime(n: int) -> bool:
            if n < 2:
                return False
            for i in range(2, isqrt(n) + 1):
                if n % i == 0:
                    return False
            return True
        
        unique_primes = set()
        
        for i in range(len(s)):
            for j in range(i, len(s)):
                num = int(s[i:j+1])
                if is_prime(num):
                    unique_primes.add(num)
        
        top_primes = sorted(unique_primes, reverse=True)[:3]
        return sum(top_primes)

The solution defines an is_prime helper function that checks primality using trial division. The nested loops generate all possible substrings, convert them to integers, and store unique primes in a set. After processing all substrings, the top three largest primes are summed.

Go Solution

import (
    "math"
    "sort"
    "strconv"
)

func isPrime(n int) bool {
    if n < 2 {
        return false
    }
    for i := 2; i <= int(math.Sqrt(float64(n))); i++ {
        if n%i == 0 {
            return false
        }
    }
    return true
}

func sumOfLargestPrimes(s string) int64 {
    uniquePrimes := make(map[int]struct{})
    
    for i := 0; i < len(s); i++ {
        for j := i; j < len(s); j++ {
            num, _ := strconv.Atoi(s[i : j+1])
            if isPrime(num) {
                uniquePrimes[num] = struct{}{}
            }
        }
    }
    
    primesList := make([]int, 0, len(uniquePrimes))
    for k := range uniquePrimes {
        primesList = append(primesList, k)
    }
    
    sort.Sort(sort.Reverse(sort.IntSlice(primesList)))
    
    sum := 0
    for i := 0; i < len(primesList) && i < 3; i++ {
        sum += primesList[i]
    }
    
    return int64(sum)
}

In Go, a map with empty struct values is used to maintain uniqueness. strconv.Atoi handles integer conversion and automatically removes leading zeros. Sorting is done using Go's built-in reverse sorting functionality.

Worked Examples

Example 1: s = "12234"

i j Substring Integer Is Prime? Set State
0 0 "1" 1 No {}
0 1 "12" 12 No {}
0 2 "122" 122 No {}
0 3 "1223" 1223 Yes {1223}
0 4 "12234" 12234 No {1223}
1 1 "2" 2 Yes {2, 1223}
1 2 "22" 22 No {2, 1223}
1 3 "223" 223 Yes {2, 1223, 223}
1 4 "2234" 2234 No {2, 1223, 223}
2 2 "2" 2 Yes {2, 1223, 223}
2 3 "23" 23 Yes {2, 1223, 223, 23}
2 4 "234" 234 No {2, 1223, 223, 23}
3 3 "3" 3 Yes {2, 1223, 223, 23, 3}
3 4 "34" 34 No {2, 1223, 223, 23, 3}
4 4 "4" 4 No {2, 1223, 223, 23, 3}

Top 3 primes: 1223, 223, 23 → Sum = 1469

Example 2: s = "111"

Unique primes: 11

Top 3 primes: 11 → Sum = 11

Example 3: s = "000"

Unique primes: {} → Sum = 0

Complexity Analysis

Measure Complexity Explanation
Time O(n^3 * sqrt(m)) Generating all substrings is O(n^2), converting to int is O(1), primality check is O(sqrt(m)), n ≤ 10 so feasible
Space O(n^2) Storing unique primes requires at most O(n^2) space as there are O(n^2) substrings

The time complexity is acceptable given n ≤ 10 and maximum integer value is at most 10^10. Space complexity is dominated by the set of unique primes, which is also limited by substring count.

Test Cases

sol = Solution()

assert sol.sumOfLargestPrimes("12234") == 1469  # example 1
assert sol.sumOfLargestPrimes("111") == 11      # example 2
assert sol.sumOfLargestPrimes("000") == 0       # all zeros
assert sol.sumOfLargestPrimes("2") == 2

Something went wrong. If this issue persists please contact us through our help center at help.openai.com.