Sum of Largest Prime Substrings - Video Solutions

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.