Sum of largest prime substrings

Hash Table Math String Sorting Number Theory

37.8% acceptance

Feb 25, 2026

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn sum_of_largest_primes(s: String) -> i64 {
    fn is_prime(n: u64) -> bool {
      if n < 2 { return false; }
      if n == 2 { return true; }
      if n % 2 == 0 { return false; }
      let mut i = 3u64;
      while i * i <= n {
        if n % i == 0 { return false; }
        i += 2;
      }
      true
    }
    
    let bytes = s.as_bytes();
    let n = bytes.len();
    let mut primes = std::collections::BTreeSet::new();
    
    for i in 0..n {
      let mut num = 0u64;
      for j in i..n {
        num = num * 10 + (bytes[j] - b'0') as u64;
        if is_prime(num) {
          primes.insert(num);
        }
      }
    }
    
    // Sum the 3 largest
    primes.iter().rev().take(3).sum::<u64>() as i64
  }
}