Skip to main content
Talentd

Sum of Largest Prime Substrings - Solution & Explanation

MediumHash TableMathStringSorting8 min readAsked at: Netcracker Technology
Practice this problem

Problem Statement

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.

Approach Overview

Problem Overview: You are given a numeric string and must examine its substrings to find prime numbers. For each relevant segment, identify the largest prime substring and add those values to a running sum.

Approach 1: Brute Force Substring Enumeration (O(n^3) time, O(1) space)

The direct method generates every possible substring using two nested loops over the string indices. Each substring is converted into an integer and checked for primality using trial division. Prime checking itself costs up to O(sqrt(v)), where v is the substring value, which pushes the total cost close to cubic when many substrings are tested repeatedly. This approach is useful for reasoning about correctness and validating small inputs but becomes slow for larger strings.

Approach 2: Enumeration + Hash Table (O(n^2 * sqrt(v)) time, O(k) space)

The optimized solution still enumerates all substrings using two pointers, but avoids repeated work. A hash table caches results of primality checks so the same numeric substring is never recomputed. During enumeration, build numbers incrementally from left to right to avoid repeated string-to-int conversions. Each candidate is validated with a number theory prime test and compared against the current maximum for that segment. The hash lookup keeps prime validation nearly constant for repeated values, reducing the practical runtime significantly.

String traversal drives the algorithm. The outer loop fixes the start index, and the inner loop expands the substring while updating the numeric value digit by digit. When a prime is found, update the tracked largest value for that region and accumulate it into the final sum. Because substring generation itself is O(n^2), this becomes the dominant cost while the hash table prevents redundant primality checks.

This method balances simplicity and performance. It relies on efficient substring enumeration from the string and constant-time hash lookups to keep the algorithm manageable within typical constraints.

Recommended for interviews: The enumeration + hash table approach is what most interviewers expect. Demonstrating the brute force first shows understanding of substring generation and prime validation. Then improving it with caching and incremental number construction shows awareness of algorithmic bottlenecks and practical optimization.

Solution

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.

After traversing all substrings, we sort the primes in the hash table in ascending order, and then take the largest 3 primes to calculate the sum.

If there are fewer than 3 primes in the hash table, return the sum of all primes.

The time complexity is O(n^2 times \sqrt{M}), and the space complexity is O(n^2), where n is the length of the string and M is the value of the largest substring.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Substring EnumerationO(n^3)O(1)Good for understanding the problem or validating small inputs
Enumeration + Hash Table (Caching Primes)O(n^2 * sqrt(v))O(k)General case and typical interview solution
Enumeration + Precomputed Prime SieveO(n^2 + V log log V)O(V)Useful when substring values are bounded and many primality checks are required

Video Solution

Q1. Sum of Largest Prime Substrings || Biweekly Contest 157 • ExpertFunda • 280 views views

Watch 7 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Sum of Largest Prime Substrings with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters