LC 3 & LC 438 & LC 567 (template)

Solution to LeetCode 3 Longest Substring Without Repeating Characters, LeetCode 438 Find All Anagrams in a String, and LeetCode 567 Permutation in String.

LeetCode 3

Longest Substring Without Repeating Characters (Medium) [link]

Using siding window and set. We choose set because we want unique characters in the substring and we are not counting occurrences. Time complexity O(n).

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        subset = set()
        right = -1
        ans = 0
        
        for i in range(n):
            if i != 0:
                subset.remove(s[i - 1])
            while right + 1 < n and s[right + 1] not in subset:
                subset.add(s[right + 1])
                right += 1
            ans = max(ans, right - i + 1)
        return ans

LeetCode 438

Find All Anagrams in a String (Medium) [link]

1] Time complexity O(nk). It exceeds the time limit because the input s string could be very long.

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        length = len(p)
        res = []
        for i in range(len(s)-length+1):
            HashTable = [0]*26
            sub = s[i:i+length]
            for j in range(len(sub)):
                HashTable[ord(sub[j]) - ord('a')] += 1
            for q in range(len(p)):
                HashTable[ord(p[q]) - ord('a')] -= 1
            res.append(i)
            for l in HashTable:
                if l != 0:
                    res.remove(i)
                    break
        return res

2] Using sliding window and dictionary.

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        len_s, len_p = len(s), len(p)
        cntp = collections.Counter(p)
        res = []
        right = len_p
        left = 0
        cnt = collections.Counter(s[left:right])
        if cntp == cnt:
            res.append(left)

        while right < len(s):
            cnt[s[right]] += 1
            cnt[s[left]] -= 1
            if cnt[s[left]] == 0:
                del cnt[s[left]]
            if cntp == cnt:
                res.append(left+1)
            right += 1
            left += 1
        return res

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        np = len(p)
        counterp = collections.Counter(p)
        right = np-1
        left = 0
        counters = collections.Counter(s[left:right])
        ans = []
        while right < len(s):
            counters[s[right]] += 1
            if counters == counterp:
                ans.append(left)
            counters[s[left]] -= 1
            if counters[s[left]] == 0:
                del counters[s[left]]
            left += 1
            right += 1
        return ans

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        len_s, len_p = len(s), len(p)
        res = []
        tab_s, tab_p = [0] * 26, [0] * 26

        if len_s < len_p:
            return res
        
        for i in range(len_p):
            tab_s[ord(s[i]) - ord('a')] += 1
            tab_p[ord(p[i]) - ord('a')] += 1

        if tab_s == tab_p:
            res.append(0)

        for i in range(len_p, len_s):
            tab_s[ord(s[i-len_p]) - ord('a')] -= 1
            tab_s[ord(s[i]) - ord('a')] += 1

            if tab_s == tab_p:
                res.append(i-len_p+1)
        
        return res

LeetCode 567

Permutation in String (Medium) [link]

Use sliding window of length |s1| to move on s2, and dictionary to determine the occurrence of characters. We choose dictionary here because we need the occurrence to be exactly the same.

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        counter1 = collections.Counter(s1)
        n1 = len(s1)
        right = n1 - 1
        left = 0
        counter2 = collections.Counter(s2[left:right])
        
        while right < len(s2):
            counter2[s2[right]] += 1
            
            if counter1 == counter2:
                return True

            counter2[s2[left]] -= 1

            if counter2[s2[left]] == 0:
                del counter2[s2[left]]

            left += 1
            right += 1
        
        return False