Leetcode 1933 Check if String Is Decomposable Into Value-Equal Substrings

Problem statement

https://leetcode.com/problems/check-if-string-is-decomposable-into-value-equal-substrings/

Solution

Let us calcualte lengths of each group of values. If we have length 0, 3, 6, 9, ...: we can separate them into groups of size 3. If we have length 1, 4, 7, 10, ... we need at least 2 groups of length 2 (in fact group of length 1 can not be seprated at all, but we can assume it it 2, because in the end we just check if it is == 1. If we have 2, 5, 8, 11, ..., then we have one group of length 2. We are happy if we have only one number from the last group and zero from other groups.

Complexity

Time complexity is O(n), space compexity is O(n) as well (space can be reduced to O(1))

Code

class Solution:
    def isDecomposable(self, s):
        lens = [len(list(j)) for i, j in groupby(s)]
        d = {0:0, 1:2, 2:1}
        return sum(d[i%3] for i in lens) == 1