判断字符串是否可分解为值均等的子串

Submission

运行时间: 30 ms

内存: 16.1 MB

class Solution:
    def isDecomposable(self, s: str) -> bool:
        # Initialize variables to track counts of 2's and 3's
        two_count, three_count = 0, 0
        i = 0
        n = len(s)
        
        while i < n:
            # Start a count of repeating characters
            count = 1
            while i + 1 < n and s[i] == s[i + 1]:
                i += 1
                count += 1
            
            # If the count is not divisible by 3 or 2, it's not decomposable by our criteria
            if count % 3 == 0:
                three_count += count // 3
            elif count % 3 == 2:
                two_count += 1
                three_count += count // 3
            elif count % 3 == 1:
                # If there's a group of 1 or any other number not fitting the criteria, return False
                return False
            
            # Move to the next distinct character
            i += 1
        
        # Check if there's exactly one group of 2 and any number of groups of 3
        return two_count == 1

Explain

该题解通过遍历字符串，统计连续字符的数量，并根据连续字符的数量来判断字符串是否可以分解为值均等的子串。具体方法是利用两个计数器，一个用于统计长度为2的子串数量，另一个用于统计长度为3的子串数量。遍历字符串时，如果连续字符组的长度是3的倍数，则增加三长度子串的计数；如果是2余数，则增加二长度子串的计数，同时也计算三长度子串；如果是1余数，则直接返回False，表示不可分解。最后，检查是否恰好有一个长度为2的子串和任意数量的长度为3的子串，满足这一条件则返回True，否则返回False。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def isDecomposable(self, s: str) -> bool:
        # Initialize variables to track counts of 2's and 3's
        two_count, three_count = 0, 0
        i = 0
        n = len(s)
        
        while i < n:
            # Start a count of repeating characters
            count = 1
            while i + 1 < n and s[i] == s[i + 1]:
                i += 1
                count += 1
            
            # Process the group based on its size
            if count % 3 == 0:
                three_count += count // 3
            elif count % 3 == 2:
                two_count += 1
                three_count += count // 3
            elif count % 3 == 1:
                # If there's a group of 1 or any other number not fitting the criteria, return False
                return False
            
            # Move to the next distinct character
            i += 1
        
        # Check if there's exactly one group of 2 and any number of groups of 3
        return two_count == 1

Explore

算法通过一个循环来遍历字符串中的每个字符，并且使用一个局部变量`count`来统计连续字符的数量。当遇到不同的字符或者到达字符串的末尾时，循环会停止统计当前字符组，并根据`count`的值来决定如何处理这个字符组。由于循环的条件是在索引`i`小于字符串长度`n`的情况下进行，且在内层循环后有`i += 1`的操作，确保了即使到达字符串末尾，最后一个字符组也会被正确处理，并根据其长度进行相应的计数操作。

根据题目的要求，字符串必须能够分解为长度为3的子串，或者正好一个长度为2的子串加上任意数量的长度为3的子串。当一个字符组的长度模3余1时，这个字符组无法被完美地分解成长度为3的子串，且留下的长度为1的部分不能单独成为一个有效的子串或与其他部分组合。因此，一旦遇到长度模3余1的情况，算法判定字符串无法按要求分解，直接返回False。这样的处理可以立即终止程序，提高算法效率。

当字符组的长度模3余2时，该组可以被分解为若干个长度为3的子串加上一个长度为2的子串。例如，一个长度为8的字符组可以分解为两个长度为3的子串和一个长度为2的子串。在这种情况下，算法首先计算可以形成多少个长度为3的子串（用整除操作），然后记下剩余的长度为2的子串。这样的处理方式确保了所有可能的子串都被有效地计数。

题目的要求是判断字符串是否可以分解成值均等的子串，其中特别说明了可能的有效子串长度只有2或3。为了满足题目的需求，最理想的情况是全部分解为长度为3的子串。然而，也允许存在一个唯一的长度为2的子串。该条件（恰好一个长度为2的子串和任意数量的长度为3的子串）是基于这样的理解来设计的，确保字符串分解后每个子串的长度要么是2（只有一个这样的子串），要么是3，从而满足题目的分解要求。