Is Sum of Largest Prime Substrings easy or hard?

The problem is typically rated Medium difficulty. Substring generation is straightforward, but combining it with efficient prime checking and avoiding redundant work requires careful optimization.

Sum of Largest Prime Substrings Python/Java solution

Most implementations enumerate substrings with two nested loops, convert digits into a growing integer value, and check primality using trial division. A hash map caches previously tested values. The same logic translates directly to Python, Java, C++, Go, and TypeScript.

How to solve Sum of Largest Prime Substrings in O(n)?

Achieving strict O(n) time is generally not feasible because the problem requires examining many substrings. Substring generation alone costs O(n^2). The best practical optimization focuses on caching primality checks and incrementally building numbers to reduce repeated work.

What is the best approach for Sum of Largest Prime Substrings?

The most practical solution uses substring enumeration combined with a hash table to cache primality results. Every substring is generated in O(n^2) time, while cached prime checks prevent repeated computation. This keeps the overall complexity around O(n^2 * sqrt(v)) in typical implementations.

Is Sum of Largest Prime Substrings asked at Google/Amazon/Meta?

Problems combining substring enumeration with prime validation appear frequently in interviews at large tech companies. Variants involving string processing, hash tables, and number theory are common practice questions for companies like Amazon, Google, and Meta.

What data structure is used in Sum of Largest Prime Substrings?

A hash table is commonly used to memoize results of primality checks so repeated numeric substrings do not require recomputation. The algorithm also relies on string traversal and number theory techniques for prime validation.

What is the time complexity of Sum of Largest Prime Substrings?

The optimized approach runs in O(n^2 * sqrt(v)) time, where n is the string length and v is the numeric value of a substring checked for primality. Space complexity is O(k) for the hash table storing previously computed prime results.

Description Hints 3 Solution Video 8:35

3556. Sum of Largest Prime Substrings

Medium37.9% acceptance1 company

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.

Example 1:

Input: s = "12234"

Output: 1469

Explanation:

The unique prime numbers formed from the substrings of "12234" are 2, 3, 23, 223, and 1223.
The 3 largest primes are 1223, 223, and 23. Their sum is 1469.

Example 2:

Input: s = "111"

Output: 11

Explanation:

The unique prime number formed from the substrings of "111" is 11.
Since there is only one prime number, the sum is 11.

Constraints:

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

Asked at 1 company

Netcracker Technology

Topics

Hints open one at a time

Hint 1

Iterate over all substrings of s to generate candidate numbers.

Hint 2

Check each candidate for primality in O(sqrt(n)) time.

Hint 3

Store unique primes, then sum the three largest (or all if fewer than three).

8:35

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def sumOfLargestPrimes(self, s: str) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

"12234"

Input

"111"

Your code is saved on this device.Solution