LC-1763 Easy LeetCode

1763. Longest Nice Substring

Hash Table String Divide and Conquer Bit Manipulation Sliding Window

Read the full problem statement on LeetCode.

Difficulty: easy Acceptance: 62% Topics: Hash Table, String, Divide and Conquer, Bit Manipulation, Sliding Window

Reading material

Arrays & Hashing 12 min Strings 12 min Divide & Conquer 11 min

Reference solution (spoiler · python)

# Time:  O(26 * n) = O(n)
# Space: O(26 * n) = O(n)

class Solution(object):
    def longestNiceSubstring(self, s):
        """
        :type s: str
        :rtype: str
        """
        lookup = set(list(s))
        prev = -1
        result = ""
        for i in xrange(len(s)+1):
            if not (i == len(s) or s[i] not in lookup or s[i].swapcase() not in lookup):
                continue
            if prev == -1 and i == len(s):
                return s
            tmp = self.longestNiceSubstring(s[prev+1:i])
            if len(tmp) > len(result):
                result = tmp
            prev = i
        return result

Solution from kamyu104/LeetCode-Solutions · MIT