M3556.最大质数子字符串之和

sliding window, https://leetcode.cn/problems/sum-of-largest-prime-substrings/description/

给定一个字符串 s，找出可以由其 子字符串 组成的 3个最大的不同质数 的和。

返回这些质数的总和，如果少于 3 个不同的质数，则返回所有不同质数的和。

质数是大于 1 且只有两个因数的自然数：1和它本身。

子字符串 是字符串中的一个连续字符序列。

注意：每个质数即使出现在多个子字符串中，也只能计算一次。此外，将子字符串转换为整数时，忽略任何前导零。

示例 1：

输入： s = "12234"

输出： 1469

解释：

由 "12234" 的子字符串形成的不同质数为 2 ，3 ，23 ，223 和 1223。
最大的 3 个质数是 1223、223 和 23。它们的和是 1469。

示例 2：

输入： s = "111"

输出： 11

解释：

由 "111" 的子字符串形成的不同质数是 11。
由于只有一个质数，所以结果是 11。

提示：

1 <= s.length <= 10
s 仅由数字组成。

python

class Solution:
    def sumOfLargestPrimes(self, s: str) -> int:
        def is_prime(n: int) -> bool:
            if n < 2:
                return False
            for i in range(2, int(n**0.5) + 1):
                if n % i == 0:
                    return False
            return True

        primes = set()
        for left in range(len(s)):
            num = int(s[left])
            if is_prime(num):
                primes.add(num)
            for right in range(left + 1, len(s)):
                num = int(s[left:right + 1])

                if is_prime(num):
                    primes.add(num)

        primes = list(primes)
        primes.sort(reverse=True)

        return sum(primes[:3]) if len(primes) > 2 else sum(primes)

if __name__ == "__main__":
    sol = Solution()
    print(sol.sumOfLargestPrimes("12234"))
    print(sol.sumOfLargestPrimes("111"))

M3556.最大质数子字符串之和 ​

M3556.最大质数子字符串之和