Leetcode 1542. Find Longest Awesome Substring

Problem statement

https://leetcode.com/problems/find-longest-awesome-substring/

Solution

The idea is calculate for each substirng s[:i] bitmask with parity of each symbol 0, 1, ..., 9. We can do it in O(n). Also for each bitmask we keep list of all places where we meet this bitmask. (in fact we need only the smallest and the biggest). Then we go throught each key and check all 10 + 1 possible neighbours: if we change one bit or 0 bits. For key and key2 we need to find the biggest distance, it is distance between ends of two segments, we can check 4 options.

Complexity

Total time complexity is O(n * m), where m is size of alhpabet.

Code

class Solution:
    def longestAwesome(self, s):
        d, ans, acc = defaultdict(list), 1, 0
        d[0].append(-1)
        
        for i, el in enumerate(s):
            acc = acc^(1<<int(el))
            d[acc].append(i)
     
        for key in d:
            x1, x2 = d[key][0], d[key][-1]
            ans = max(ans, x2 - x1)
            for i in range(10):
                key2 = key ^ (1<<i)
                if key2 in d:
                    y1, y2 = d[key2][0], d[key2][-1]
                    ans = max(ans, abs(x1-y1), abs(x1-y2), abs(x2-y1), abs(x2-y2))
                        
        return ans

Problem statement

Solution

Complexity

Code

Remark